Hey Azmo thanks for the quick reply.
Your idea of combining and tweaking real world names is a good approach.
In my setting there is a region where I really wanted to have 'englandish' names, so I opened up Google Earth and zoomed in on ye marry olde England to get some inspiration for the names. I ended with some of the following names.
Gouthster
Blythelford
Leighbury
Milwick
Crawlind
Dormould
I've also used some words from my native language (Danish) for more outlandish names, there is a barbarian horde called Umulig, which means impossible in Danish.
Anyway here are the two maps for my setting. One is a world map and the other encompasses the kingdom of Dothnia and the immediate region, where the campaign takes place.
World map
Map of Dothnia
In the campaign you are an initiate of the Shadow Shields, a covert order sworn to protect the Dothian crown and the integrity of the realm at all cost (wow, how original, I know

)