Are there conventional expressions in Latin to strengthen the question, showing total surprise or perplexity? How do you say, for example, "What the heck...?" or "Why on earth...?" in Latin?
One way of expressing surprise is to add the word nam to a question, which seems to add a sense of "... and I really have no idea what the answer is". Lewis and Short (section III of the entry) describe this use of nam as "expressing wonder or emotion in the questioner". Nam often follows the interrogative pronoun quis and is written together as one word, quisnam, which can be translated as e.g. "who in the world?" or "I wonder who?":
Quidnam id est?
What in the world is that? I wonder what that is?
It's often difficult to match idioms exactly between languages, but in at least one case you mention Latin has an almost exact equivalent: Ubi terrarum...?
non edepol nunc ubi terrarum sim scio (Plautus, Amphitruo 336)
Now I don't have a clue where on earth I am.
Quid istúc est? aut ubi istúc est terrarum loci? (Plautus, Asinaria 32)
What is this? And where on earth is this place?
Obviously, it is also possible to pair adverbs (Quid nunc? Quid iam? -What now? Cur edepol, mehercle? -Why in heaven's name?) or insults (Quid, insane, rogites...? Quid, verbero?) to the question.
As an addition to the answers already given, tandem after interrogative might be added for the sake of emphasis, like nam (in TKR's answer), but might be even stronger.
According to Lewis and Short (I.B) it has the flavor of adverbial pray in English, so it not necessarily expresses "total surprise or perplexity" so-strong as in the sense of "what the heck?" (though, it might), but it clearly strengthening the question.
This source, while explaining tandem, also mentions dii boni, that might be translated as "for heaven's sake":
quamquam o dii boni! quid est in hominis vita diu?