What I have:
What I want (where vertices are connected and merged, I do not believe Ctrl+M is what I want, I don't have the right options):
Blender Stack Exchange is a question and answer site for people who use Blender to create 3D graphics, animations, or games. It only takes a minute to sign up.Sign up to join this community
Alt+M is actually what you are looking for... just select a pair of vertices and hit Alt+M. Make sure you choose the right option. I tend to use Last and keep that in mind when selecting, to make sure my vertices get merged at the right point.
Alternatively, you could enable vertex snaps (bottom right of your 3d view: click the magnet icon and choose vertex from the dropdown list next to it), snap the misplaced vertices to their expected destination vertex, select both the moved vertex and the "destination vertex" and then hit Ctrl+V and choose the Remove Doubles tool.
This will achieve the same thing in a larger amount of steps. Remember to disable snaps by clicking on the magnet icon once you are done using them, they can be quite bothersome if you don't.
What I would do is select the 4 vertices which you want to create a face from and press F then select the unwanted vertices or edges, press X then select dissolve vertices or edges.