If this actually happens, it will trigger a constitutional crisis. This Slate article speculates that the only likely actions would be resignation or impeachment.
The President will likely voluntarily resign if he is "honest, law abiding, and not dismayed". Apart from that, only Congress can impeach and remove a President from office.
The Supreme Court is not able to initiate impeachment proceedings, as Article I Section 3 of the US Constitution states that the Senate has the "sole power to try all impeachments":
The Senate shall have the sole power to try all impeachments. When sitting for that purpose, they shall be on oath or affirmation. When the President of the United States is tried, the Chief Justice shall preside: And no person shall be convicted without the concurrence of two thirds of the members present.
And the Supreme Court decided in Nixon v. United States that the federal judiciary cannot review impeachment proceedings, and thereby cannot remove a President from office.
Significantly, the framers of the Constitution explicitly considered, but turned down, a role for the Supreme Court in the initiation of presidential impeachment proceedings.
As for the actions the President had taken, it will be left to the Supreme Court to decide on the course of action, since it would be unprecedented.
It's worth noting, someone who is a US citizen at birth but was not born in the US is likely eligible to serve as President.
Related question: How is it that Ted Cruz can run for the U.S. presidency seeing as he was born in Calgary?
This question came up when Ted Cruz ran for President in 2016 as he was born in Canada. The 2008 Republican presidential nominee John McCain is also born outside of the US, in Panama.
Since the Constitution only states that a President needs to be a "natural born citizen", "most legal experts contend it means someone is a citizen from birth".
If that’s the definition, then Cruz is a natural born citizen by being born to an American mother and having her citizenship at birth. The Congressional Research Service, the agency tasked with providing authoritative research to all members of Congress, published a report after the 2008 election supporting the thinking that "natural born" citizenship means citizenship held "at birth."