It's still pretty uncertain at what point in the game you can start building one.
I suspect if RNG blesses you, it was hinted you might find ancient remains of megastructures lying around! How soon could you fix or build your own? If it's just the Ascension Perk, perhaps it can be worked on sooner. Even if Max Starport will be a requirement, Orbital Megastructure like Sensors, Science and Habitat before year 2300 could be a thing.
I suspect Sensor and Science might actually be doable as soon as you finish first Tradition tree and pick their Ascension Perk. Time will tell!
I think the perks will adress some worries of mine that an already far-flung empire will build them just to consolidate, as there might be better Ascension Perks for them than the Megastructure ones. It's on the list as some of the possible things they could do, but it's not the only things they could do, at the end of the day.
EDIT: Time will tell, once we know with what other Ascension Perks and opportunities Megastructures compete with.