There is a story about Alexander the Great visiting Jerusalem. This story is not supported by other sources, as far as I know, and so is probably not literally true (it may well reflect some interaction short of a visit). I also recall reading (in an old Cambridge volume, I think) about a Greek city (possibly on the shores of the Black Sea) which had a legend about Alexander visiting it and reforming its laws - once again, the visit being practically impossible given what we know about Alexander's itinerary and schedule.
Are there other examples? I am asking about legends recorded in antiquity, not the numerous highly imaginative medieval stories about Alexander.