Egyptians in the New World?

[Nathan Ross]

but of course the desert between Marocco and Senegal was not what it is today.

Maybe so, but there's still about 1180 miles between the Atlas and the Senegal, and that's more or less in a straight line. Equivalent to marching from Constantinople to the Rhine - and then they'd have to do the same distance back again! Unless they had some pressing reason to do so, I doubt a Roman commander would take his men so very far.

Your point about the Carthaginians having elephants also suggests that elephants were found much further north - in southern Morocco perhaps? - and that Paulinus wouldn't have had to go quite so far to find them.