How can I clearly detail all possible destinations from every point of the map in my game?
I would suggest putting hexes on the map.  Players can then know how far one city is from another by counting the hexes.  As long as the numbers are small such as 4 or 5 it would not provide too much complexity.
This is how Railways of the World solves this problem, and it works really well

The advantage of hexes over any other shape is that they remove any problems with diagonal movement.  Cities are a natural distance apart from any angle.  Counting the smallest number of hexes to get from one stop to another is always accurate.