My theory is that she didn't send him back in time to before he obtained the Spiritual Stones, because if that had happened, the Door of Time would have still been closed.
So, she must have sent him back to before he first pulled the sword and allowed Ganondorf into the Sacred Realm, where he still had the stones. Then, he must have returned them all to their race's keepers, and automatically closed the Door of Time.
The reason he's a legend is because of helping the Gorons enter Dodongo's Cavern, rescuing Princess Ruto from Jabu-Jabu's belly, and possibly providing the warning that allowed the Hylians to find out what Ganondorf was planning before it ever happened.
Maybe he didn't just tell Zelda, maybe he found out a specific, incriminating place that Ganondorf would be, and got witnesses to lie in wait there, gathering enough evidence to prove he was after the Triforce.