Both phrasings refer to an action that occurred in the past (his going). The additional nuance you need to consider here is whether the question itself sounds like it occurred in the past. A question that is part of the narrative should sound like a past question, just like the other events you report.
"Where had he gone?" fits in with the past-tense telling of the story. While yes, you could imagine someone asking "where had he gone?" in a present-tense setting, it's not the most natural formation. With "where had he gone?", both the going and the asking are in the past.
"Where did he go", while referring to an action in the past (his going), sounds like a question in the present. "Had gone" is a marker for the past perfect (completed action), while "did go" sounds like a still-current action. (I am desperately reaching for proper grammar terms here and failing. Sorry.)
Consider this example: you're standing on a street corner minding your own business when a suspicious-looking person carrying a bag of money runs past you. Soon after a policeman arrives and asks you about the person he was chasing. What do you think he asks you? Most likely "which way did he go?" -- indicating a current question.
You are telling a story of past events, so you want the question to come across as a past event too, in order to fit in. Therefore, "which way had he gone?" will fit better in your narrative if it is the narrator who's asking the question.
Another approach would be to have a character ask the question (possibly your POV character asking himself mentally); if your character asks the question as a question in the story, then "which way did he go?" would be better because from his point of view the situation is current and active. If you do that, use the standard dialogue markers -- either or both of quotation marks and something like "he wondered" or "he asked himself".