Could you please explain what is the difference between them?
Où means where. Où allez-vous ? : Where are you going?
D'où means from where. D'où venez vous ? : Where do you come from?
Why don't we use "À où allez-vous?"?
Because it is not idiomatic and the à wouldn't add any piece of information anyway.
Combinations with où are possible though, as Gilles commented:
À partir d'où la frontière commence ? : From where starts the border?
Jusqu'où va la route ? : How far does the road go?
Vers où partent-ils ? : Where are they heading? (literally: "toward where...")
You can still use à this way:
À quel endroit allez-vous ? : Where are you going (literally: "To what place are you going?")
Is it correct to say "Où sort-il?"?
It is correct French but has a different meaning (where does he go out/does he leave).
Note also that like with my previous examples, the inversion is more a written or formal way to express the negation.
Usual spoken French would be: Il sort où ? Ils partent vers où ? La frontière commence où ? La route va jusqu'où ? Vous allez à quel endroit ?