Oh, yeah, I missed that part. Being that the case, an AG with a carefully tailored fitness function, or a more specific implementation of the Ant Colony might do wonders after running overnight
I'm really curious to see the results, I'm betting that amazingly believable and organic roads would follow.

Maybe assume that the larger the city, the earlier it was founded (or provide city age as well) and do the road finding progressively by time. That way, as new roads to new villages are being created, some old ones might become abandoned, and roads that are well used for a very long time will be marked as better developed (paved with stones and wider).

Of course, if your goal is to save time, this is not the way to go Maybe the MST+A* way will be wiser for that purpose.