It sounds like you are doing a top-down approach. Have you tried looking at it from the bottom up?

So for example imagine a village in one of your countries. What would they call the local region and how big is that "region" to them? Does it stop at the big river to the west and then beyond that, they call it something else? And is the region they live in important enough to be named on a map by those ruling over them? (like if they are a prosperous region known for their vineyards they might be worth noting on a map but if it's just a scattered bunch of small farming communities - perhaps not so much). Do they speak a different language or a dialect several towns and villages down the road? If so they will be called something else and so will the area they live in.

You could try approaching it like that.