From what I'm hearing PotA is supposed to follow after Phandelver, which my group has done, but we're all level 5 now. I've been trying to track down if they have a smooth transition for this, but no one seems to be able to answer that question. What little I've seen is that it starts from level 1.
There are a number of optional quests around Red Larch designed for 1st and 2nd level PCs. The actual Elemental Evil storyline begins at 3rd level. That being said, 5th level PCs should be fine. The first few missions might be a little on the easy side - although you could always add a few more baddies to each encounter to compensate - but once they catch up to where they should be in terms of level, everything will be fine. 