Should か be replaced with の? Should I say 買った instead of 買いました?
Make any sort of corrections you want, I'm trying to make my Japanese sound as native as possible.
It's grammatically perfectly correct, but whether or not it sounds natural depends on the situation. If you're asking this question to your colleague, your sentence is perfectly natural as-is. If you're asking this question to your boss or a guest, you need to use proper keigo, like "その靴はどこでお買いになりましたか?". If you're asking this to your friend or family, then you would speak much more informally, like "その靴どこで買ったの?".