Do you replace tokens moved to the Trade Route mat?
You do not replace the coin tokens. So with Colonies in the game, and no other extra victory cards, yes, four is the maximum number of coins on the mat. Remember that there potentially are other victory cards among the kingdom cards in the game, though, depending on what expansions you're playing with - like Gardens from the base game, and many others.

Why? Because the card doesn't say to. If you're ever having trouble with Dominion rules, just read the card carefully, and do exactly what it says in the order it says.