English is not my primary language, as such I have some difficult trying to understand the actual meaning of some place names.
Shadowfell is the place where "shadows (noun) fell (verb)", or is a place with creatures that are "shadow (adjective) and fell (adjective)", or even a place with creatures with a "shadow (adjective) fell (noun)"?
Underdark is place where people live "under the dark[ness]", or a place that is "under [the ground] and dark"?
UPDATE
I think I know understand enough to make concessions and come up with some more descriptive (and correct) terms for the main regions of D&D in Portuguese:
Feywild: Its a wilderness that inhabited by fey creatures, therefore: "Selva Feérica" (Fey wilderness).
Shadowfell: Its a fell (moor) that is shadowy, therefore: "Pântano Sombrio" (Shadow Swamp).
Underdark: Its a dark region thats below ground, therefore "Escuridão Inferior" (Under Darkness).
I could try make some wordplays, but I think it would be trading a more correct meaning and interpretation for some witty words that might looks like it means nothing. Also, portuguese if not very good on making composite words such as fey-wild, shadow-fell, or under-dark.
UPDATE 2
New definitions, more abstract and appropriate to planes or "worlds":
Feywild: It's magical, misterious, beauty, and somewhat dangerous, therefore: "Fascinação Feérica" (Fey Fascination);
Shadowfell: It's dangerous, dull, moor'y, cruel, and decaying, therefore: "Desolação Sombria" (Shadowy Desolation);
Underdark: It's dark, deep below the ground, and somewhat hellish, therefore: "Escuridão Profunda" (Deep Darkness).
UPDATE 3 (FINAL)
New definitions, more literal and keeping in line with the same english style (compound name made of adjective-adjective):
Feywild: "Feérico-selvagem" (fey-wild);
Shadowfell: "Sombrio-desolado" (shadow-desolate);
Underdark: "Profundo-escuro" (deep-dark).
Using this last schema allow for some wordplay since I have two adjectives any of them might take the part of being a noun. Also, is allow for other place names to follow the same "rule", eg Feydark/Feérico-escuro.
Best Answer
The place names actually have a bit to do with the actual geography of the location. @dpatchery does a good job summing up what the places are, since you asked about the linguistic nature of the place names, I'll elaborate a bit further.
The short answer is all of your interpretations are valid, and have to do with the authors doing an intricate play-on-words here.
The Shadowfell
In terms of primary meaning, I would say that "fell" here primarily is an adjective meaning "fierce; cruel; dreadful; savage". Since the Shadowfell is a rather harsh place, and filled with shadow creatures, I would the authors were using that as a primary meaning. On the other hand, your interpretation of "Place where Shadows Fell", could also be correct, as the whole land itself is shrouded in a gloom.
Underdark
As @AceCalhoon notes, I agree, this is a place which is underground and dark. However, the interpretation of "place which is under the cover of darkness" is also generally accurate, as not very much light gets down there.
So in short, basically your interpretations are all "correct", and I think it was rather witty word-play on the part of the authors.