They were a bureaucratic society. To cross the central rainforest and the Kalahari desert to trade with South Africa and do not reflect it in their documents seems unlikely to me (but I'm not an expert in this field).
This said, finding a wild Nicotiana in Egypt today is a childs game. Nicotiana glauca, an escaped american species appears everywhere in all Mediterranean countries. Could easily slip into any local plant mix aiming to give some good ol' autenthicity to a modern mummy.
The first ships likely capable of making a crossing are the Chinese junks, followed by Polynesian outrigger canoes. The first European ships capable of making it are probably the Viking longships, which makes pre-Viking contact difficult to conceive, much less a sustained trading pattern. Furthermore, Phoenician ships were predominantly rowed, not sailed, which makes the journey especially hard to believe.
Thanks!