## Depends on the infrastructure ##

The travel time would be highly dependent on the available infrastructure. Furthermore, the sea lanes and rivers would be very important - the differences can be enormous, and it's often faster to take a water route that's twice as long on the map as opposed to going over land; *especially* if you want to bring any goods or supplies and not just a person or message.

However, a useful tool that may help you is experimenting with the [ORBIS model of travel throughout the Roman empire][1], which was rather well documented - pick circumstances that are similar to your story, and it will give reasonable estimates. Two weeks overland on horseback in good conditions on reasonable roads can cover ~800 km / 500 miles. 


  [1]: http://orbis.stanford.edu/