I'm going to guess that those are a different species to a North African forest elephant.
http://en.wikipedia.org/wiki/North_African_elephant
This would be a HUGE exercise in patience as it has been said, but there are a few circumstances that could pull it off.
As mentioned, the Carthaginians had tamed African Elephants, and they did range that part of N.Africa. Another region was just south of Kush. We could have it so that an incredibly talented Pharaoh, be they Kushite, or Egyptian, or Greek has some imported to the Faiyum, or sets up a colony on the very edge of "Elephant Territory" - they would have the wealth and the money to pull this off without just saying "A dude did it".
The main thing is that Elephants aren't tamed unless there is a value to it, and the resources. Egypt has the grain perhaps - and the masonry blocks to shift, but they are difficult to import (unless we look at the Sudanese Coastline). Where else is there a purpose?
If we see a masonry civilisation emerge in the heart of Africa, they could begin using Elephants to build incredible walls, temples and shrines once they tame them and put them to work. I could see any "Worker Gods" having Elephant features in such a society, but also potentially the image of "Kings" as Elephants could be the symbol of power.
All in all, I'd expect societies with a much more monumental scale of construction, or to fight warfare largely focused around controlling Elephants.
Personally, I push for anyone ever doing a storyline with Egypt or Africa involved prior to the Romans, to remind the ruler NOT to wipe out the North African Elephant. Just doing this could lead to the obvious - Elephant Assisted construction of the Suez/Pharaohs Canal. Humans digging + Elephants moving dirt, rock, and canal facing = Epic Win.
The idea of taming elephants, or the techniques could be transmitted to Africa via the Garamentes trade routes. They may not own Elephants, but if someone with the skills to tame elephants survives disease contact with Sub-saharan africa could well tame elephants, teach the natives, and later have these skills used for more than just warfare.
Side note : Elephant Caravanserai would be AWESOME. Both in cool, and in the size of the buildings!