Or the Epoch is involved. Again, I agree with the probability but this is one thing we simply cannot accept as fact until full proof is given.
The problem is that there is no full proof ever given to any of the theories that we have.
Here at the Chrono Compenidum, we put two and two together, see what sources are consistent and how they're related to make ends meet.
Magus went back to 12,000BC - CT FACT.
Lucca dismantled the Epoch - Most likely as it wasn't needed, and if it got into the wrong hands, you get the point (she said she would in one of the endings).
Belthasar seemed to have had some contact with Lucca - CC as Belthasar and Lucca worked on the Promethius Circuit. Belthasar probably informed her that Robo would be in FATE, so Lucca wanted to change the original Mother Brain intellegence so that FATE wouldn't be naturally rogue so maybe Robo could live safely (failed though).
Lucca emphasizes that Magus would have found Kid - And the only way of doing that is by going to the present day.
In RD, Magus can time travel - He searched all time periods till he found her.
And RD isn't direct canon, but it details Magus quite well, what he did, what happened.
If they purposely made Magus have time traveling abilities, then as to the overall story, Magus is intended to have them, just that he didn't appear in CC for us (they didn't want him like overloading the game with his easter egg cameo appearance)
And as for his age, he looks pretty young in Toriyama's prints. Most likely 20ish. He did appear sometime before 600AD and was about 8 at the time. I don't think that it'd go past him to kill Cyrus around the age of 12-16. After all, Crono and co are 16ish and they owned pretty much everyone in the game.