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.