A character achieves Legend status by True Reincarnating twice. This is a 36-point build (32 points for drow).
This is displayed in your character's examination panel, as a sort of tip to other players that you have put a lot of work into your character. Your character will also be very slightly taller than a hero build. True Reincarnating any further won't grant additional build points or make your character taller, but you can still gain additional past lives feats, eventually leading up to Completionist if you get them all.
Legend character on non-VIP account (Premium/Free to Play) can open quests on all difficulties including Casual, Normal, Hard, Elite and Reaper. No need to be unlocked via completion or store purchase.