I never did figure out what the right answer was in traditional grammar, but I ended up reading in a linguistics paper somewhere that this is a complementizer. In other words, it turns a clause into a complement of the following verb.
In your example, it turns どこにある into an interrogative complement of the verb 知っています:
As for the department store, where is it?
= Where is the department store?
2. デパートは [ どこにあるか ] 知っていますか？
As for the department store, do you know [ where it is? ]
= Do you know where the department store is?
In the first example, か turns the clause into a question. In the second example, か turns the clause into a complement of the main verb 知っています.
This complementizer is specifically interrogative, which means it's applied to interrogative clauses. For example, this could mean a clause that contains a question word, such as だれ, なに, どう, or なんで. And when I search for
か知って in the Balanced Corpus of Contemporary Written Japanese, all the examples I find do contain this sort of question word, so I think it's a fairly common pattern. But based on @dainichi's comments below, it seems that it can also be used more generally. Right now, my guess is that it can be used with any clause that can be interpreted as semantically interrogative.
So, even if we replace どこ with a non-question word like ここ, your question is still grammatical, because ここにあるか is still interrogative:
3. デパートは [ ここにあるか ] 知っていますか？
As for the department store, do you know [ whether it's here? ]
= Do you know whether the department store is here?
So far, it might seem like this か is pretty similar to the question-forming particle か. But unlike the question-forming か, complementizer か can follow the copula だ. Take a look at the following example:
4. 赤い帽子をかぶったあの女性、[ 誰だか ] 知ってる？
The woman in the red hat, do you know [ who she is? ]
= Any idea who the woman in the red hat is?
(example adapted from ALC)
Example 4 is grammatical, even though you wouldn't normally end a question with だか, so we can see that they're somewhat different.
I have one more example, which is from a question I asked not too long ago. I found a sentence that ended in だか, but as we just discussed, the question-forming か can't follow だ. So I asked whether 知らない was omitted at the end:
And Darius Jahandarie, who answered the question, agreed that this was a correct way to read the sentence. So I think this is one more scenario where you can see the complementizer か rather than the question-forming か.