In my world, a population of vikings, one of the groups who landed on North America in the 9th and 10th centuries, was driven inland by a party of natives and holed up in a cavern that they found.
As far as I know, phrases such as "What in the world" and "What on Earth," and other phrases that deal with the Earth were not commonly used in the time of the vikings.
My question is this: What would these modern day vikings say instead of these phrases? What on Cavern?
There's a bunch of false assumptions in the question.
First, they're Vikings and should be using Nordic idioms, not English ones. Do modern Scandinavians use "what in the world?" as an exclamation? What did Vikings use? You should find out. I'm willing to bet there's a lot of swearing by the gods and also raunchy body parts.
Second, idioms do not have to retain their literal meaning, that's why they're idioms. In fact, most do not have literal meaning. People underground can still say "what on Earth" and it doesn't matter that they're technically inside the Earth. For example, I'm an atheist but I still say "oh my god".
Another example is "high". Now it's primarily used to mean a physical height, but "high" was used in the sense of "important". We have all sorts of words and phrases which retain that otherwise lost meaning. "Highway" now means a multi-lane road with no traffic lights that cars drive on, but it's not elevated in the sense we use "high" today. It originally meant an important road. Also "High Street" (in the USA that would be "Main Street"), "high horse", "high-handed", "high school", "high time", "high noon", "high finance", and "high and mighty".
As for how the exclamations of an isolated society would evolve over 1000 years, that's a whole other question.
Presuming that the audience/readers are native English speakers I see no reason not to subvert English idioms. Subverting an idiom your audience has never heard of sounds pointlessly confusing.
I think a simple mashup of the two gives an obvious meaning, makes it distinct, and reminds one that the speaker comes from a different perspective:
What in Earth?
How about "What in Midgard?"
https://en.wikipedia.org/wiki/Midgard
Midgard (or "Middle Earth" as it is in a popular fantasy book you may of heard of) could have for these people a more literal meaning of the "middle of the earth" while it would also allow them to maintain some of their original viking heritage as it is a tradition viking word.
Like @Schwern said, idioms are not literals. I'll try to answer this a few ways, but they all come down to much the same point.
You might find the paper useful/fascinating, titled "What is it like to be a bat?", which covers this ground. Quick outline:
The author asks from a philosophy viewpoint, what it's like to be a (speculatively blind) bat who uses sound "chirps" instead of vision. The author concludes roughly, that the bat would probably think of it as we do sight, by what it provides rather than by how it happens (do we think of photons when we see?).
In the same way, your inner living people will have a term (several terms?) meaning "this land/place/surface we live in/on", and whatever term they use, which might be Nordic, or a completely original word, would be used much as we use "earth".
The fact we use "earth" as an expletive doesn't relate to "earth as round planet in space", it relates to "earth as known land people can live on/are aware of". "Earth" itself doesn't (or didn't until recently) mean "planet in space" either.
So you need to decouple meanings here. When we say "what on earth" we aren't using a term that is based upon knowledge of a round planet whose exterior we live on, or anything like it. We are using "what on earth" to signify "what is this, which seems so unlikely that it should not exist on the places we know and are aware of, and live in" (or something along those lines).
So coming back to your question, they may have a similar expletive referencing their term for "all known places", they may not have expletives at all, or they may have a term for it that isn't itself meaningful otherwise such as "what in zlobbbttki" or whatever, a symbol they use for "all the universe except for the bits the gods watch TV in", or whatever outlandish terms cultures has led to.
Terry Pratchett would have been more imaginative, I think. The upshot is, don't assume/expect a direct parallel and if one did exist then the word could be anything people might come to use after centuries of linguistic isolation.
