Как во времена Средневековья выбирался врач, который будет следить за здоровьем короля? По заслугам, образованию, происхождению, протекции?

Убеждена, что в расчет брались все пункты вами указанные, но, очевидно, в определенной последовательности.

Безусловно, чтобы стать претендентом на право называться «архиатором», «первым медиком» или «физиком», а именно так называли королевских врачей в XIII - XV веках, надо было получить достойное образование. Медицинские факультеты в университетах Европы появляются практически с момента их возникновения, примерно, с XII-XIII вв. Париж, Монпелье, Утрехт, Оксфорд, Болонья, Упсала и многие другие города могут похвастаться существованием старейших медицинских школ.   А столетием ранее в Италии и Испании под арабским влиянием появились медицинские школы. Законченным считалось следующее образование: полный курс лекций (около 5 лет) в одном или в нескольких университетах, несколько лет медицинской практики, кроме того, всячески приветствовались научные занятия ботаникой и анатомией.

Но это был только первый шаг. Позволить себе полное обучение детей могли только зажиточные люди, что не исключало и наличие покровителя или покровителей, которые материально поддерживали одаренного студента. Кроме того, это было гарантией постоянного притока состоятельных пациентов. Покровители и благодарные больные становились зачастую стартовой площадкой выдвижения того или иного медика на высший уровень в своей профессии. Достижение такого положения сопровождалось не только всеми положенными привилегиями, но и могло трагически закончиться в случае, если коронованный пациент или кто-то из его окружения умирал. Так, например, произошло с врачом Ивана III приезжим иноземцем Антоном Эренштейном, которого за неудачное лечение сына касимовского царевича Каракачи зарезала его охрана.

Безусловно, свою роль в достижении должности первого врача государя играл и послужной список претендента. Так, например, успехи в хирургии Анри де Мондевиля и рекомендации профессора, у которого он обучался в университете Парижа, позволили ему в 1301 г. стать придворным врачом французских королей Филиппа IV и Людовика X. Матиас де Лобель был не просто известным врачом в Нидерландах и известным ботаником, но и в течение нескольких лет являлся личным врачом принца  Вильгельма. Его авторитет, опыт и научные публикации стали основанием для того, что в 1607 г. он был приглашён стать личным врачом английского короля Якова I.

Первый отечественный архиатор и лейб-медик Петра I Роберт Карлович Арескин, к моменту поступления на русскую службу имел за спиной и прекрасное образование в Эдинбургском университете, и многочисленную практику, что сразу привлекло внимание князя А.Д. Меншикова. По его рекомендации, а также впечатлившись организаторскими и врачебными способностями Арескина император Пётр назначает его лейб-медиком, а также поручает ему создание кунсткамеры, ботанического сада и университетской библиотеки.

Историй подобных тем, что здесь приводятся, довольно много и они со всей очевидностью подтверждают то, что при назначении врача на должность лейб-медика свою роль играли и происхождение, и протекции, и деньги.