Best way to handle movement input?

How about implementing a stack of states rather than a single state machine? Events and callbacks (updating, input, drawing, etc.) are sent to the topmost state. If they're unhandled, they're passed to the next state, etc.

For example, your character only has the IdleState on its stack. This handles movement as well.

So if the player hits a directional key, this adds another state, e.g. MoveNorthState. This state will handle the transition/animation and remove itself once done.

Let's assume there's a toggle to make your character take flight. So once you hit the hotkey, the state FlightState is added. FlightState won't handle movement, so input events related to movement are passed down the stack to IdleState, which will once again add a state, e.g. MoveSouthState.

If your FlightState notices the hotkey for state change to be hit, it will remove itself from the stack and pass control back to the state below (typically IdleState).

Of course this has other potential problems, like trying to modify some state in the middle. You'll have to come up with proper states and flags/status fields. Don't create a state for every tiny bit, just because you're able to.