"Where is the soldier walking to?" is not an appropiate answer?
Because "where ... to?" asks about the destination of his walking, but hol in Hungarian only refers to the location where he is walking around in.
Asking about the destination rather than location would be hova/hová according to hatcher's comment above.
Why is "Where walks the soldier" incorrect?
Because in modern English, we ask such questions with "do"-support: "Where does the soldier walk?"
Omitting "do" is archaic or poetic, not normal 21st-century language.
Thank you for the explanation!