What incentive would Marth have? He's rebuilding a nation, he's kinda busy. What incentive would Alm have? He's fighting his own war.
Just because he's rebuilding a nation doesn't mean that Marth isn't going to travel abroad. He still has to maintain good relations with his allies, and possibly even find new ones. He's probably going to welcome all the help he can possibly find.
How would they even learn of eachother?
Word of mouth. I doubt Paola, Est, and Katua are the only ones who made the journey from Akaneia to Valencia. It seems unlikely that there wouldn't be any sort of trade between the two continents. Trade requires people obviously, and people are likely to bring stories from their homeland to the places they travel