The BOE is not taken to get the rank of commander, it's taken to be allowed to take command on the bridge. Harry was taking command on the bridge since the beginning so he most probably passed it back in the academy. I doubt he would have been allowed a bridge position if he hadn't passed the Bridge officers exam since he was a bridge Officer.
The BOE is apparently required for a rank of commander, as then-Lt Commander Troi in "Thine Own Self" is required to pass the BOE in order to be promoted to full Commander. On the other hand, it is possible that the BOE is only required for non-command division officers who are interested in (bridge) command situations.
The second point is mostly conceded, considering he was serving as a bridge officer. However, due to the wide latitude Starfleet Captains are routinely allowed in discretion, I would also add that one may not necessarily have needed to pass the BOE in order for the Captain or an agent acting in the Captain's stead to give a specific officer the command chair.
Bashirs Boss was a commander. Bashir wasn't even on a Federation base. The Station was in orbit of Bajor (in the pilot) which had millions of Doctors on it.... "hundreds?"
The rank of the station's CO is irrelevant to Bashir's rank, as is the presence of Bajoran doctors on Bajor (IIRC, the planet was about three hours away by runabout, after all). Since the station was under Starfleet administration, none of those doctors would have "outranked" Bashir, even though the station was owned by Bajor.
Bashirs "starfleet" crew he had to look after was tiny (a few dozen?). Bashir's staff was almost nonexistant. However, it was his first posting straight out of the academy and... Bashir was not an Ensign.
In 2369 ("Captive Pursuit"), the station housed approximately three hundred individuals, all of whom Bashir would've been responsible for as CMO of the station. Presumably that number continued to increase from that point forward, considering it was only the sixth episode of the season and travel to the Gamma Quadrant had yet to begin in earnest. In addition to the fixed population of the station, Bashir would have been responsible for visitors. You're correct that he was not an ensign; he was a lieutenant (junior grade), only one step above ensign.
Ezri was also instantly promoted to Lieutenant when her counsellors degree came through.
It was lieutenant (junior grade), actually, and the promotion came through at the behest of Captain Sisko, who also arranged for the remainder of her training to be waived. Ezri Dax, therefore, was an unusual situation, an anomaly (and, after all, a joined Trill with eight previous lifetimes of experience, one of which had been as a highly respected diplomat). If she had not transferred to DS9, she would've returned to
Destiny and assumed, as she noted several times, an
assistant ship's counselor position.
If Kim got his MD, he was standing on the only federation ship inthe quadrant, he had a 150 people to look after and was expected to "cure" planetary level stuff ups and while doing this he needed authority on the ship to do everything he needed without waiting for permission from his superiors...
I'm sure he would've been promoted; completing a medical degree is, after all, an achievement worthy of recognition with a rank higher than ensign. However, I dispute that there's any reason to believe that he would've automatically been elevated to lieutenant commander, and there's even less to believe he would go from ensign to full commander. There's no reason he would skip anywhere from two to three entire grades in rank, especially since Bashir, as second in his class, graduated as a lieutenant (junior grade), not a lieutenant commander.
His nurse (by season 4) is a fricking lieutenant!
This is not necessarily indicative of a need for him to be ranked higher than lieutenant in this hypothetical situation, however. As CMO, his position would obviously be more important than rank, which is why a lieutenant (jg) can give orders to superior officers in medical matters. As such, the rank of his (part-time, let's face it; Paris, the helmsman, was wrong choice for a nurse) nurse would be immaterial when compared to his position.
What was the rank of the original Doctor? [...] And IMDB also says that his name is Fitzgerald which almost confirms the rank.
Non-canon sources and IMDB do not confirm anything. As the section you quoted pointed out, his name and rank were not given in the script or in dialogue. The information submitted to IMDB could as easily come from the "Caretaker" novelization or the CCG. As it so happens, however, you don't need either to prove that he was indeed a lieutenant commander, as
this screenshot on MA does show him to be ranked as such.
The MD position on Voyager REQUIRED a lieutenant commander and ther's very little getting around that (Co-hologram-ough) because the job was too hard for a lieutenant but too easy for a commander.
That said, we do
not know with any certainty that the CMO position on
Voyager "REQUIRED" that rank. For all we know,
Voyager's CMO was already a lieutenant commander prior to his transfer to that ship. Considering Bashir was CMO of a station with approximately three hundred individuals living on it, I see no reason to presume that
Voyager's CMO position "was too hard for a lieutenant." After all, as you pointed out,
Voyager's complement was approximately one hundred fifty individuals when the ship set out for the Badlands,
half the number of souls Bashir was responsible for at the beginning of his CMO tenure. Nor could it have been "too easy for a commander" because a medical officer would have needed to take the BOE to advance to that rank, as Beverly Crusher discussed with Deanna Troi.
To distill my point down to a very basic form: I think your hypothetical situation made a lot of assumptions that were unfounded in terms of rank and promotion. The premise of the idea, however, is intruiging. Watching a character, whether it was Kim or someone else, undergo the training and education necessary to move into a radically different discipline than they had originally trained in could've been a very interesting ongoing characterization choice.
