The braisa quoted in the gemara says that a talmid chacham has precedence in being redeemed from captivity over a king because he is harder to replace. Anyone can be king (it is like being president). The mishna seems to concur because after the entire list of priority, it says that a chacham has precedence over even a kohein gadol. Of course it is possible that the mishna deliberately doesn't mention a king, it is difficult to say that the mishna would disagree with the braisa. This makes the Rambam in his commentary to the mishna very difficult to understand.
The Rambam writes:
וזה שטעם קדימת חכם למלך אינו אלא באמונה בלבד לפי שהחכם תועלתו לאומה גדולה מאוד, אבל במעשה אין להקדים על כבוד המלך שום דבר ואע"פ שהוא עם הארץ שנאמר שום תשים עליך מלך
The Rambam somehow manages to consider the priority of a Torah scholar over a king to be merely theoretical, but claims that in practice a king would still have priority. What does the Rambam mean by this and how does he explain the fact that the braisa lists the priority of a chacham over a king in an actual situation of redemption from captivity?
Although I don't have a full understanding of how the Rambam can do this, it seems to me that the peshat in the Rambam is that he understands that the list of the mishna and braisa is a list of who is more important and/or more essential. Most of the time the more important/essential person should be saved before the other. However, when it comes to a king there is a specific obligation of שום תשים עליך מלך- שתהא אימתו עליך, to show fear and awe for the king. Although the king may be less essential, there is a specific obligation that would demand of every Jew to prioritize the king even at the expense of the more important Torah scholar. Therefore, when faced with a situation the Rambam holds that the king must be prioritized and this idea of the chacham being more important is "only b'emuna" - only in assessing his objective value, but not in practice.