Правильно: Восточная Украина. В полном академическом справочнике «Правила русской орфографии и пунктуации» под ред. В. В. Лопатина (М., 2006 и более поздние издания) сформулировано следующее правило: «Названия частей государств и континентов, носящие терминологический характер, пишутся с прописной буквы, напр.: Европейская Россия, Западная Белоруссия, Правобережная Украина...».

В первом случае местоимение притяжательное, во втором - личное.

В первом примере его – притяжательное местоименное прилагательное (отвечает на вопрос: чей подвиг?)

Во втором примере его – форма винительного падежа личного местоимения он (отвечает на вопрос: наградили кого?).

Действительно, существует особая группа территорий, представление о которых включает исторический, политический, этнический, культурный, эстетический и пр. компонент, в отличие от собственно географических (природных) территорий, названия которых не содержат никаких дополнительных коннотаций. Например, Балтия — это не территория вокруг Балтийского моря, а Латвия, Литва и Эстония, связанные с Россией общей историей; под Восточной Европой понимают не просто часть европейского континента, а часть, населенную преимущественно славянскими народами. Север — полярные и приполярные территории, Арктика. Но сочетание Юг России в написании с заглавной буквы закрепилось в русском культурном фонде как название территории, подконтрольной белогвардейцам в 1918—1920 гг., ср.: Вооруженные силы Юга России — объединенные вооруженные силы Белого движения, образованные 8 января 1919 г. в результате соглашения между командующим Добровольческой  армией А. И. Деникиным и атаманом Донского казачьего войска П. Н. Красновым. Только в таком значении и следует писать с заглавной буквы Юг России.

Верно: о его.

О короле: спросил.

Названия можно подвести под правило о территориальных и административно-территориальных единицах и писать оба слова с заглавной буквы (ср. Ближний Восток).