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, 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.