They are both correct, and either could be used in the majority of situtations.
However, "start moving" is in command form, where as "begin to move" is an action. Therefore, you could use 'start moving' in a sentence with a command, such as:
"You must start moving now."
'Begin to move' is NOT a command. For example,
"I told Johnny that if he doesn't begin to move in gym class, the teacher will be very angry."
I hope this helps. Sorry if it's a little confusing!