I've done a fair bit of reading today on the relevant works, and while it doesn't look like there are any time travel stories directly involving C-3PO, I was surprised that there's actually 2 straightforward answers in the Canon:
Alderaan (or On board the Tantive IV)
Time Travel and Teleportation are rare, but both are possible in the Star Wars universe.
C-3PO's primary function is "etiquette and protocol", and he is the personal property of Bail Organa, Prince of Alderaan. We see protocol droids performing hospitality duties similar to what you might expect personal assistants or hotel staff to do, such as TC-14 in The Phantom Menace.
So if Luke had asked the same question(or any other question) at C-3PO's "day job" of facilitating diplomacy for the Alderaanian royal family, C-3PO most likely could have directed him to someone better equipped to answer the question, or an archive where he could research it himself.
There is a means of manipulating time and travelling through space in the Jedi Temple on Lothal.
Not long before A New Hope the Emperor expended considerable resources trying to control this means of time travel.(Star Wars Rebels: A World Between Worlds)
C-3PO's other job at the time of A New Hope is working for the Rebel Alliance. We see C-3PO as R2-D2's cover story while on a secret mission in Star Wars Rebels: Droids in Distress, and we see the two of them in the hangar on Yavin 4 in Rogue One.
The idea that there are planets on which time travel is possible (or at least that the Emperor believes that there is) would therefore not be surprising to him, as a translator for one of the Founders of the Rebel Alliance.