For me, when I was creating my world, names were kinda easy.
A few examples:
Empire of Brighton, saw the name Brighton on a sign post as a street name.
Ferringio was just a play on the name Ferigno (guy who played the Hulk on the TV Series).
As I got older (yes that campaign world is over 20 years old), I started thinking, how do we, as humans in the real world come up with city names? In our English speaking culture we have a tendency to name them after eaither people, other places (England has York, The US has New York, England has Jersey, US has New Jersye, France has Orleans, US has New Orleans), or after prominent physical/environmental features: Swiftwater, Bridal Falls, etc.
So, Kingdom names aside, place names are easy.
The name of the Human city should be First Landing (as Grey Fox was saying to me the other day), because it makes sense from a entymolgical point of view. Its where the first arrived, it would be their biggest settlement, as a lot of the first timber for construction would have come from the dismantleing of the ships they arrived on, etc.
A web search on Toponymy (the scietific name for the study of place names), brought me this little gem regarding place names in Britain:
Places were originally named in Old English, Norse, Scots, Welsh, Gaelic or Cornish, according to landscape features (topography), nature of settlement (habitat – city, town, village, fortifications) or the people or tribe living in the area, often combining two or three descriptive terms in one name. These names were then influenced and modified at various historical periods through language shift driven by socio-economic and political changes.
These sometimes introduced new language influences, such as French from the Norman Conquest.
So, if you have names for towns villages, etc called Walden's Bridge because some guy named Walden built a bridge and a village srpung up there because it was a good crossing point, so be it. Even the name of the game "Neverwinter Night" is based on the city of Neverwinter in the Forgotten Realms, so named because even though it is far north, it seldom experience Winter in it;s full force.