Once you level to 60 you become Legendary, it has nothing to do with Quest finishing, it is all about Wizard level. If you finished all your quests-including side quests you should easily be Legendary by the time you do Crustean Empire.
You need more experience to keep leveling up. Yes, go back and do all the side quests you can - you get more experience points on quests than some random fights.
I hit legendary way before I finished Celestia - did all the Zeke, crafting, and side quests. But while helping someone the other day in DS, I saw a guy with a mark over his head so I had missed 1 side quest. And I have a lot of Grizzle yet to do.
So - there are more than enough quests to get you to legendary - just find them and do them. :)
Nora RavenSong lvl 60 balance Ellie NightWeaver lvl 42 death Lenora LionHeart lvl 37 myth Lenora DrakeMancer lvl 19 fire