There's a lot of history packed into these few lines:
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.
Firstly, I think it more likely that Dehner's statement about working with Gary for years is targeted against Spock, not Kirk nor a general "you". Secondly, Kirk has been friends since Gary joined the service indicating many more years than Spock working with Gary. Thirdly, Kirk asked for Gary for Kirk's first command, but I don't see the Enterprise as Kirk's first command since I doubt that Starfleet would give anyone their "first" command on the most important ship in the fleet, rather, they should have proved themselves on other command(s).
My scenario for
WNMHGB:
< circa April 2265> Kirk is newly promoted to Captain rank, takes a little time to catch up to the Enterprise since she's in deep space, then arrives on board at a starbase (I have Kirk's arrival less than two weeks before the episode based on stardates on the tombstone; but stardates are another topic). Kirk takes over command of the Enterprise because Pike is promoted to Fleet Captain. The Enterprise is sent on a mapping mission to go beyond the on the edge. It is not on a five year mission. (I sometimes think that in-universe, there is no such thing as a five year mission, rather, Starfleet's practice to refit it's Starships every five years, but again, that's another topic.)
Kirk inherits all personnel we see in WNMHGB from Pike; Lt. Cmd. Spock is first officer (and not dueled with the Science Division Head position; Number One has moved on probably years before the episode), and by chance, Kirk's old friend Lt. Cmd. Gary Mitchell on the helm and already on the ship for 2+ years at this time serving with Spock. Spock must have "liked" Mitchell since he felt for him when he died.
Kirk's past friendship with Mitchell predates Starfleet Academy. Once back together at Starfleet Academy, their relationship seems to involve high adventures together that includes womanizing. There's a good chance that they both served together for a while on another ship (perhaps on then Cmd. Kirk's first command on some lesser ship) when Michell took the poisoned darts for him. It's Mitchell and not Kirk who seems familiar with Kelso. I get nothing from Kirk about long term working and familiarity with Kelso. Same with Sulu.
As for how long has Kirk and Spock known each other? It seems they may have been on the peace mission to Axanar together when Kirk was a cadet (we see cadets serving on starships in the Cage, so, there's a chance that cadet Kirk and Ensign/Lt. Spock were on the same ship), and/or maybe they met during the Vulcanian Expedition. There can be some fond old memories of Spock. Maybe they got together several times through the adjoining years while at Earth or on occasional Starbases to foster a closer friendship, perhaps over their love of chess and other intellectual matters. Kirk is happy to have Spock as first officer and enjoys getting reacquainted with him over chess.
< circa May 2265> Shortly after
WNMHGB, UE's Starfleet Command moves under the UFP to take over joint Space Command of all members (possible reason for Pike's promotion): issues new uniforms; resets the Stardate clock cycle; plans a new age of 5YMs if it really is a thing). Details of the transition of UFP members’ ships/starbases/assets are still in committee.
< circa Sept 2265> Enterprise is ordered back to Spacedock for refit for a 5YM. Kirk/Spock/Scott oversee the refit. McCoy, Chapel, Uhura and Rand join during the refit. Sulu returns in time for its relaunch.
< circa Sept 2266> The refit Enterprise is launched for the regular series. YMMV

.