You are correct about か expressing uncertainty. In this case, the phrase どこか is an 'indeterminate pronoun' which indicates the presence of something unknown. どこか can be translated in English as 'somewhere' (or 'anywhere' depending on the context). Other examples of indeterminate pronouns are 誰か (someone), 何か (something), どれか (one of...), いつか (some time), etc. The use of particles (を, で, に, へ, etc) following these words depends on the context. Sometimes they can be omitted and other times, they cannot. But let's stick to your example sentence and your specific questions.
In your example, 冬休みはどこか行きましたか, replacing [か] with either [へ] and [に] would actually change the meaning of the sentence from "Did you go anywhere during winter break?" to "Where did you go during winter break?". You could not use [が] because verbs of movement (such as 行く) require the particle に or へ. Finally, you could add [へ] or [に] to make 冬休みはどこかへ行きましたか, which does not change the meaning (see other examples here).
Finally, a note about omitting particles following どこか. Sometimes particles are omitted in casual speech, for example. I searched the BCCWJ corpus for instances of どこか with 行く (including verbal inflexions). There were many more instances of どこかへ行く and どこかに行く than どこか行く, with particle omissions often occurring in quoted speech. In other words, it is more usual to see どこか with a particle attached. In other cases, you need the particle. For example, with どこかでその広告を見ました, you must include the particle で. So it is context-dependent.