Isn't Spock who the "You've known Gary for years" line is directed at?
KELSO: Well, it didn't make any sense that he'd know, but naturally, I checked out the circuit anyway. I don't know how, but he was right. This point is burned out exactly the way he described it.
DEHNER: Sorry I'm late. I became so interested in observing Gary, Mister Mitchell.
SPOCK: Our subject is not Gary Mitchell. Our concern is, rather, what he is mutating into.
DEHNER: I know those from your planet aren't suppose to have feelings like we do, Mister Spock, but to talk that way about a man you've worked next to for years is worse than
KIRK: That's enough, Doctor.
DEHNER: I don't think so. I understand you least of all. Gary told me that you've been friends since he joined the service, that you asked for him aboard your first command.
From this we know Spock and Mitchell have worked together for a while and Kirk has known Mitchell since he joined Starfleet.
So either Spock and Mitchell served together on a ship before the Enterprise or they've been on the Enterprise together for over a year ( or two). Which might mean Kirk was the CO of the Enterprise for a year or two prior to WNMHGB.
The Chronology is often too "on the nose" when it comes to dates.