Same can be said for Shatner, but people tend to ignore that one.
Shatner was, according to "Star Trek Lives," scheduled to direct the final episode of the Original Series in 1969. Unfortunately, that would have been Episode 81, and NBC sent the word down during the filming of "Turnabout Intruder" that that episode, #79, would be the last.
The Other Darrin: Kirstie Alley loved playing Saavik (she apparently wore the ears home a number of times) and wanted to return, but apparently failed to communicate this clearly to her agent, who demanded a higher fee for her to play Saavik than Paramount was willing to pay. Paramount switched in Robin Curtis instead.
Early scripts has the Klingons as a rogue group who commandeered a Romulan Bird of Prey.
And earlier than that, it was supposed to be Romulans, period, in Harve Bennett's treatment. Spock's role is relatively the same, except he goes feral and kills several Romulan miners when they drill for dilithium on the Genesis planet. A subplot would have also had the Vulcans threatening to secede from the Federation over the Genesis Torpedo...
In the novelization, Saavik and David Marcus became romantically involved (the seeds for this were planted in the previous movie's novelization); this storyline was completely dropped from the films.
In the novelization, Saavik became pregnant with Spock's kid. This, too, was dropped.