Ross' previous adjutant before he made Sisko his adjutant was also a captain. (Captain Bennet, if I remember correctly.) Promoted to command a tactical wing, but it was never stated if it was just a position promotion or it had a rank boost, as well.
Admiral Leyton's was a Commander, Benteen. She was promoted to captain and given command of the Lakota. (Though given the events of "PARADISE LOST", I can see her losing that promotion at the least... possibly even out of Starfleet.)
An adjutant seems to be at least 3 steps lower in rank than their direct superior.