The answer is pretty much the same for casual games, Regular REL, Competitive REL, and Professional REL, but there are minor differences.
For casual games, the rules simply state that the action is reversed. That means, you undo the action.
CR 729.1 If a player takes an illegal action or starts to take an action but can’t legally complete it, the entire action is reversed and any payments already made are canceled. No abilities trigger and no effects apply as a result of an undone action. If the action was casting a spell, the spell returns to the zone it came from. Each player may also reverse any legal mana abilities that player activated while making the illegal play, unless mana from those abilities or from any triggered mana abilities they caused to trigger was spent on another mana ability that wasn’t reversed. [...]
At Regular REL, the judge rewinds the game to just before the spell was cast. From the JAR:
A player makes an in-game error not mentioned above
[...]
If the error was caught quickly and backing up is relatively easy, you may undo all the actions back to the point that the illegal action happened.
At Competitive and Professional RELs, the casting of the spell is reversed by "simple backup". Your opponent (the player who made the error) receives a Game Rule Violation. If you fail to catch the error in a reasonable time then you receive a Failure to Maintain Game State Violation. You didn't say how much time passed, but I'm going to assume you realized within a few seconds, and so you would not receive a violation. From the IPG:
IPG Section 2.5, Game Play Error — Game Rule Violation
Additional Remedy
First consider a simple back up (see section 1.4)
IPG Section 1.4, Backing Up
Some remedies state a simple backup may be performed. A simple backup is backing up the last action completed
As for your "bonus question", it does not change the situation at any level of play. Even though your opponent has taken two actions now, none of the other remedies for Game Rule Violation are more suitable than a full backup of both actions.