It should be noted that by Kirk's time, even relatively nearby places like Pollux/Beta Geminorum were unexplored by Starfleet or the Federation - yet relatively faraway places like Omicron Ceti were human colonies.
It would appear that the shape of explored space was not that of a perfect sphere with the radius defined by the range of the starships. Rather, it would be like a sea urchin, with long, very thin (and probably oddly curved) spikes heading out into the depths of space, leaving massive unexplored volumes in between. How far the farthest of those spikes reached is a matter of debate, as is the issue of whether Kirk would have been responsible for the farthest sortie.
For example, in "Where No Man", Kirk claims that no Earthship could possibly have come that far (to a place from where it would be a short hop to leave the galaxy) before the Enterprise. He is proven wrong, of course - but even then, we cannot tell whether Kirk meant "no Earthship this far from Earth" or "no Earthship this far in this direction".
If we accept the former, then that's probably the farthest Kirk ever went (but sadly, we don't know how far that is). If the latter, the next candidate might be Rigel, some 900 lightyears away - but we know at least Pike went there before, and so did McCoy at some point in the past. Trelane's mad little world was also 900 ly from Earth, perhaps indicating that Kirk (and other Starfleet heroes?) regularly traveled that far.
The heroes also know about Denebian slime devils, which might hail from the star Deneb/Alpha Cygni, some 3,000 lightyears away by modern reckoning. But nothing indicates the heroes would have traveled that far themselves...
As for the center-of-galaxy thing, which Kirk did both in ST5:TFF and TAS "Magicks of Megas-Tu", it could be either accepted as a record (about 26,000 ly from Earth by modern reckoning) - or contested as an impossibility and explained away as an instance of going towards the core, but only a fraction of the way. But if Kirk actually went to the rim of our galactic disk, this would be an equal feat of some 25,000 ly - and Kirk did it thrice in TOS and once in TAS.
However, as regards this rim thing, it should be noted that the straight line between the Milky Way and the Andromeda galaxy would not run through the rim of the Milky Way, so the trip depicted in "By Any Other Name" would have involved penetrating the barrier at some lesser distance. No such helpful data is available on the other three instances, alas.
Timo Saloniemi