Spoiler alert: Starter Set "Mines of Phandelver"
I'm worried that somehow they'll find their way to Wave Echo Cave without having done enough missions to level up to level 4 as it appears to require.
First off, it's not clear that they can reach the Wave Echo Cave at all without the required map. In fact, given that this very valuable mine has been hidden for centuries, I think it's safe to assume that basically nobody knows where it is unless they have the map.
There's an off chance that the Banshee could tell them, but it's not clear that she would really know. Consider that if the Banshee did know or was expected to know, then the NPC would have sent them there to ask that question instead of the one about the book.
So I think it's safe to assume that the PCs won't just "wander up" to the caves.
... without having done enough missions to level up to level 4 as it appears to require
To be clear here, the XP stuff is just a "recommendation". You can always just give your players level 4 when they are finally ready to progress. My players finished the main quest (just last night) did basically none of the side quests. In fact, they found Cragmaw castle early, so they went: Goblins, Cragmaw, Redbrands, Wave Echo. When I knew they were going to Wave Echo cave, I just gave them level 4 instead of making them wander around just to "level up" like it was Final Fantasy.
Likewise, I don't consider the rest of the adventure to be a waste. In fact, I'm planning to use the other side quests as hooks for the main upcoming adventure and I'm going to scale for their level. At level 5, there's actually a reasonable chance they can beat the Green Dragon, especially with some power-ups from the Mine. Wyvern Tor is easy to upgrade and is likely a hook for the next adventure as the "upgrade" will involve a third party.