There isn't really a good set of top-down rules for this. But it may be helpful to walk through a series of examples. Since you appear to be familiar with Skyrim, I will use their hold names. While reading this, it may prove useful to consult this map:
Winterhold is just "winter" + "hold" - a very logical name given that it's a hold located in the far north of the province (and therefore very cold). Similarly, Eastmarch lies along the eastern border of Skyrim (the term "march" means "a border region"). The Rift lies in Skyrim's southeast, bordered by the Velothi and Jerall Mountains. It is presumably named for the rather large pass that lies between the two mountain ranges, at the southeastern tip of Skyrim, or possibly for the more prosaic fact that it is a low-lying area surrounded on most sides by mountains. Hjaalmarch includes much of the River Hjaal and Whiterun much of the White River. Hjaalmarch also follows the coast, and its name (containing "march") suggests that Haafingar may once have been a separate polity, or at least that Hjaalmarch and Haafingar may once have been at odds with each other.
The remaining holds are less obvious to me, but the point is that, both in fiction and in real life, places are often named for their geography. So you can often start by figuring out the names of the local rivers (rivers are always extremely important in the early stages of civilization), the climate, local flora and fauna, etc. It's also a good idea to have a basic understanding of where the political boundaries of your world lie, how they have changed, and how they would have interacted with geographical features. Think carefully about which of these aspects are likely to have had the greatest influence on the people living there. Finally, go through a thesaurus, and look at different synonyms for the local geography. Most of the time, using a thesaurus is risky, because it can lead to using overly complicated or rare words, but in the case of place names, we care a great deal more about how nicely it scans than about how easy it is to understand. Nevertheless, you should also consult a dictionary to ensure that you don't get too far away from the correct meaning.
Ultimately, there is a fair amount of trial and error here. You may need to experiment with several different names before you hit on one that you actually like. If you are not a native English speaker, this will be harder, because it may be less obvious to you what "sounds natural" to an Anglophone ear. If you have an English-speaking friend, you could try the names out on them, but if not, then you might just have to make do as best you can. Of course, there's always the option of writing in your first language instead of English.
