I really hesitate to use Marc Cushman as a reference but his "These Are the Voyages: TOS Season Two" is here on my unread pile, and there are Coon memo interpretations (and some direct quotes, just not for this factoid) in here. Pages 292-293 discuss that "Coon wanted to bring back John Colicos - Kor from 'Errand of Mercy'. He felt a recurring adversary for Kirk would be good for the series. But Colicos was unavailable to take the job so Coon called another actor he was fond of, and who had worked well in 'Star Trek' before."
Cushman's claim in this instance is not backed up by a memo or a script reference, but I thinks he's badly paraphrasing (without citation) a claim that appears in David Gerrold's book about "The Trouble with Tribbles." Consult the following passage about a potential reappearance of Captain
Koloth (page 255 of my copy, first printing, May 1973):
An interesting sidelight to this is that Gene Roddenberry had been thinking that Kirk should have a Klingon counterpart. Just as the Enterprise is assigned to a specific quadrant of the galaxy, so would a specific Klingon ship be assigned by the Klingon High Command to the same quadrant. Thus the two captains would continually find themselves confronting each other. Roddenberry had thought William Campbell as Captain Koloth might be perfect for this role. Campbell would then have become a semi-regular, appearing in every story where Kirk confronted Klingons.
Unfortunately, Campbell was not available the next time a Klingon episode was to be filmed, so another actor was hired. Later on, the idea of a continuing set of nasties was dropped or forgotten.
The next episode to feature a Klingon character was "A Private Little War." What we know about that episode is that Don Ingalls' first draft story outline featured Kor, Bob Justman complained, and starting with Ingalls' second draft story outline, the Klingon character was changed to Krell. This all happened in May of 1967, long before William Campbell was cast in the role of Koloth. No story or script for "A Private Little War" features Koloth in it, nor do I have any existing memo where including Koloth is even discussed.
Perhaps Roddenberry confused Koloth with Kor (who was slated to reappear, at various stages, in both "A Private Little War" and "Day of the Dove") when he told Gerrold this—
if he told Gerrold this. Or maybe this is a flattering lie Roddenberry told to William Campbell, who was a regular poker buddy with James Doohan and Gene Roddenberry (which would help explain how they both ended up in the Roddenberry-produced
Pretty Maids All In A Row), and then Campbell relayed to Gerrold. Who knows.