...which continues to ignore the emphasis of distinction Commodore Stone placed on serving as a starship captain [etc.]
Except not. I am arguing that Kirk is not a special starship captain, not that starship captains would not be special (for a given value of special - say, nobody can deny that the captains of airliners today are special, but declaring them famous as a category gets us nowhere).
This holds fully within Starfleet, where nobody expresses the idea that Kirk would have recognizability (whereas e.g. Pike and Tracey do). Furthermore, nobody thinks the Enterprise has recognizability. This only changes after the first couple of movies - although primarily because the first couple of movies did not yet feature characters other than the main heroes and therefore provide no information on the subject.
At this point in series (in-series) history, Kor had not laid eyes on Kirk, but he knew who he was and the ship he commanded. Furthermore, Kirk and his ship's reputation was so established that Kor has--apparently for some time--hoped to meet Kirk in battle. No one dreams of fighting random officer of cookie-cutter vessel.
This touches on the issue from what one might consider the other end. The lowly Günther Prien and his midget fighting vessel U-47 were famous adversaries even if deep below (har har) the COs of German capital ships, and said ships, in internal rank and prestige. Could Kirk become a famed warrior (which is a status assigned him by Garth of Izar, although apparently for antics preceding Kirk's first command by a wide margin) without being a prestigious top leader in command of a great ship? Obviously, as per precedent.
We already know other Klingon captains--such as Koloth and Kang--were also very familiar with Kirk and his ship, which strongly points out (not really necessary with all of the episode evidence) that Kirk and his ship were always on the front lines, "being a thing" in the galaxy, which is not an opportunity shared by any ship.
Or then these buddies of Kor had a "thing" with the man who humiliated their friend.
Even though the timetable of said friendship is far from established, two Klingons being familiar with the opponent of a third is a very specific and narrow type of fame, thus not necessarily in conflict with the fact that inside Starfleet, it's very much "Kirk who?" at the time.
Continuing, the Romulan Commander from "The Enterprise Incident" were also well aware of Kirk and his ship:
So, she was not referring to Spock or Vulcans, but Kirk and his ship. No run-of-the-mill vessel or commander earns the attention of an enemy government or its fleet officers by name and/or reputation.
...This time we actually witness the specific event giving Kirk this specific and narrow type of fame before any indication of the fame appears. "Errand of Mercy" may have made Kirk a Household name for Klingons, but we can tell for certain that "Balance of Terror" did that for Romulans. Indeed, they'd be starved for household names after a century of isolation. Kirk killing Sarek's long-lost cousin is like a random clown from the Police Academy movies solving a crime after a century of no crime, reflecting not a bit on how great a man this hero-of-the-day really was. Except in Kirk's case it wouldn't even be news for the hero side, which does similar heroics every Tuesday..
...according to what TOS on-screen source? Stone made it clear that being a starship captain was a rare distinction not anyone could do. There's no getting around that line.
Being a fighter pilot is that today. I'm not saying Kirk would not be comparable to a fighter pilot. I'm saying his USAF does not consider him an ace, even when it thinks Pike is decorated and Tracey is experienced.
Nothing in TOS establishes the number of starship captains. Everything outside TOS indicates the number to be high, and to include truly insignificant people.
Do note my continuing use of "in Starfleet", please. There's a continuing and total lack of evidence that Kirk would be a recognized name within that organization, even if he automatically is "less common" than Ensign Nowan and her zillion co-Ensigns by virtue of seniority in a pyramid hierarchy.
Then, there's the Babel conference--even the laziest of observers would not miss that the Enterprise (with Kirk in command) was selected to carry the Mount Rushmore/United Nations of Federation ambassadors and dignitaries to the conference if the ship and crew were not considered the best representation of the Federation's Starfleet. They did not call up Wesley, Tracey, the Defiant or Intrepid captains for such an important, high-security mission. They tapped Kirk and his Enterprise.
What was distinguished about the skippers who hauled Allied leaders around in WWII? Sometimes they were run-of-the-mill battleship COs, which is special within a navy; just as often, they were run-of-the-mill cruiser COs, which is not special within a navy. And Kirk flies a cruiser, and a small one, as per onscreen (even if TOS-external) evidence.
Playing chauffeur to VIPs is a job that may call for a "photogenic" driver with socializing and PR as part and parcel of his job - or then not. From Kirk's other chauffeuring jobs, we know he's not photogenic, but rather the underappreciated servant of self-conscious top men. Does anything in "Journey to Babel" suggest differently for that particular case? He invites nobody to his Captain's Table, and gets no attention from the delegates. Starfleet did not send him for his recognizability, then. For his competence? Sure, but surely competence should not be considered special!
Clearly, TOS (and TAS to a certain degree) established Kirk and his ship as special not only within Starfleet, but to the Federation's greatest enemy governments.
We never met anybody from the Federation's enemy governments, so how could we tell?
Timo Saloniemi