It would have to go through the federal judiciary, yes, and rise to a level such that the court's decision would be binding nationwide on the question of eligibility on that point of evidence. The exact cause of action and method would vary by state.
In my state, each candidate for President and Vice President merely have to swear an affidavit that they are eligible for the office. Other states have more stringent requirements. Upon evidence, an aggrieved party may make a complaint in federal court asking for declarative relief in the form of the court's declaration that a candidate who "has been twice elected" is ineligible, despite the affidavit. That declaration could be tested in theory all the way to the Supreme Court, which would ostensibly rule on such silly questions as we've had in this thread regarding whether they have to be consecutive or not, etc. That aggrieved party might be a rival candidate. It might be the state attorney general, although there would have to be some wrangling to determine exactly how the state was injured. Article III requires "standing," which means a particularized injury.
The same would hold for other elements of eligibility, such as citizenship and age. Someone who appears old enough can plausibly swear an affidavit attesting to his eligibility. But if legally cognizable evidence were found to challenge that affidavit, then again the question would go to federal court for the facts to be tried and a determination made. Such an outcome in all cases might be a writ of mandamus instructing the "federal election officer" in each state (the lieutenant governor in mine, the secretary of state in most others) to remove the candidate from the ballot.
It is, and I've read Erskine May.