Where It All Goes Down
Mapping the Magi
Let's get real.
The Magi are moving, approximately, from the area just north of present-day Saudi Arabia—so, nearish to the Persian Gulf—towards the Mediterranean and present-day Israel. Since "Journey of the Magi" begins by noting how cold it is, and since Persia really doesn't have winter to speak of, we can tell right off the bat that the Magi are nearing the end of their journey and so must be relatively close to Bethlehem, which is right next to Jerusalem. (It's about halfway between the Mediterranean and the Dead Sea, if you're interested.)
Based on lines 17-18 and then 21, we can figure out that the poem starts with the Magi approximately two days' travel away from Bethlehem. (Which isn't all that far, considering they were traveling on camels.) So the bulk of the poem, then, takes place in the valley that contains Bethlehem and Jerusalem, both of which are hugely important cities to the Christian faith.
Poetic Places
But all that's just geography. What does it mean for our poem? For our Magi, the setting is ten kinds of miserable. Think the worst backpacking trip you've ever been on. It's dirty, you're freezing, your group is bickering amongst itself, and every time you run across anything resembling civilization, it's even worse than the camping has been. No good. The end of your destination is a little better—at least you're not getting snowed on—but it's still not the world's friendliest place.
Things get a bit confusing in that last stanza. But if we look at line 41, we can see where the Magus says "these Kingdoms." Based on that, we can reasonably assume that he's speaking from his palace, years after the original journey. So we can also infer, from the beginning of the poem, that it's probably hot, and sunny, and luxurious as he's relating this tale. The Magus doesn't really seem to be reveling in it by the end of the poem, though, so maybe the setting here is less important than his state of mind.