Да, это сочетание плеонастично, т. к. привилегия — исключительное право пользования чем-либо, предоставляемое кому-либо в отличие от других. Тем не менее сочетание это встречается и в публицистике, и в художественной речи, ср.: Валерия рассуждала с такой убежденностью, точно ей была дана исключительная привилегия знать и объяснять, что делается на небесах (М. Н. Волконский. Гамлет XVIII века. 1903); Но создание новой культуры — исключительная привилегия Советской власти, ленинской национальной политики («Химия и жизнь». 1969).

Правилами орфографии не регламентировано написание частей роуд, таун и под. в составе географических названий, так как эти части в русском языке являются экзотизмами. Это лексически не освоенные слова, они называют реалии зарубежной жизни. Выбирая написание, нужно ориентироваться на контекст. Если в тексте географические названия с этими частями встречаются несколько раз, если читатель может воспринять их как нарицательные слова со своими значениями, то нужно выбрать написание со строчной буквы. Так, например, в статье Е. Замятина, опубликованной в сборнике 1988 года: Образ этот неверен потому, что хороший шофер безошибочно проведет свой автомобиль даже в Лондоне ― от Стрэнда до Юстон-роуд. Если же предполагаемый читатель в контексте воспримет иностранное вкрапление как часть названия, то правильно написание с прописной буквы. Способствует такому восприятию наличие родового слова перед названием, например: В два часа ночи «Ренессанс» закрывался, но неуемная компания желала ехать «дальше», в открытые до утра кабаки на далекой улице Ханьчжоу-Роуд, в западной части сеттльмента, в районе загородных иностранных клубов (Н. И. Ильина).

Есть, это форма небеса.

Астанский – устаревшая рекомендация. Название Астана относительно новое, и прилагательные от него образовывались разными способами. Эти колебания нашли отражение в словарях. Согласно словарю Е. А. Левашова «Географические названия» (СПб., 2000) от слова Астана образуются прилагательные астанинский и астанийский. Современный академический орфографический словарь фиксирует только вариант астанинский, который, по-видимому, получил более широкое распространение. Прилагательное астанайский закрепилось в церковной сфере. Официальные названия – Астанайская епархия и митрополит Астанайский.

Правило, на которое Вы ссылаетесь, – орфографическое. Оно регулирует только выбор гласной буквы в прилагательных на -нский, образованных от имен собственных.

На это предложение есть несколько возражений.

Во-первых, слово поп в русском языке обозначает именно православного священника, причем не является нейтральным. В словарях оно дано с пометой «разговорное» и нередко используется в контекстах, где речь идет о каких-либо негативных качествах священника (жадность, наглость и др.).

Во-вторых, папа римский — это не просто священнослужитель, это глава католической церкви. Слово поп такого значения не передает.

В-третьих, Вы сами пишете: по устоявшейся традиции. Традиции в языке очень сильны, и сочетание папа римский давно устоялось в русском языке для обозначения главы католической церкви. Нет никакого смысла это менять, да язык и сам не позволил бы нам это сделать.

В словарях современного русского языка найти слово великославный нам не удалось. Однако оно зафиксировано во втором выпуске «Словаря русского языка XI–XVII вв.» (М., 1975), а также встречается в Ветхом Завете (Третья книга Маккавейская, глава 6: Тогда великославный Вседержитель и истинный Бог, явив святое лице Свое, отверз небесные врата, из которых сошли два славных и страшных Ангела, видимые всем, кроме Иудеев) и в исторических сочинениях П. Н. Крекшина, новгородского дворянина, служившего при Петре Великом в Кронштадте («Экстракт из великославных дел кесарей вост. и зап. и из великославных дел имп. Петра Вел.», «Экстракт из великославных дел царей и вел. князей всероссийских с 862 по 1756 г.»). 

Мы, конечно, не можем признать слово великославный употребительным сейчас, в современном русском языке. Однако нельзя исключить, что в каких-то текстах (возможно, религиозной тематики) это прилагательное встречается. Значение его вполне понятно, так как образовано оно по существующей в современном русском языке модели (ср.: великославный – имеющий большую славу, известный, знаменитый и великодушный, великовозрастный). В древности таких слов было еще больше. Например, в «Словаре русского языка XI–XVII вв.» отмечены великоребрый, великосильный, великомышленный, великомудрый, великодушевный, великозвучный. 

Подобные двукорневые слова часто оказываются заимствованными в русский язык из старославянского, где они создавались специально для перевода греческих слов, состоящих из двух корней. Так, например, появилось прилагательное единородный (ср. с греч. monogeneses  от monos 'единственный' и geneses 'рождение'). 

Прилагательные с суффиксом -ск- со значением ‘относящийся к тому или свойственный тому, что названо производящим словом’, характеризующие те или иные территориальные объекты, образуются от названий континентов, стран, населенных пунктов и других понятий, связанных с жизнью и деятельностью людей, например: австралийский, узбекский, московский и т. п.

Ср.: горы → горный (относящийся к горам как природному, географическому явлению) и горы → горский (относящийся к горам как к месту обитания человека).

Названия сторон света — это нарицательные существительные, обозначающие географические понятия, поэтому от них образуются прилагательные с суффиксом -н-: север → северный, юг → южный, запад → западный, восток → восточный. Прилагательные с суффиксом -ск- не образуются.

Существительные с суффиксом -анин-/-янин- (во множественном числе -ан-/-ян-) имеют значение ‘житель или уроженец местности, названной производящим словом’, например: россиянин (россияне), волжанин (волжане), парижанин (парижане), селянин (селяне), марсианин (марсиане) и т. п.

Понятия север и юг связаны с Северным и Южным полюсами Земли, а восток и запад — с вращением Земли вокруг своей оси и видимым движением небесных светил. Соответственно, в первичном нарицательном значении север и юг связаны с определенной территорией, а восток и запад — нет. Поэтому в литературном языке есть словообразовательные пары север → северянин (северяне) и юг → южанин (южане), а наименования жителей, образованные от слов восток и запад, отсутствуют. Использование слов Восток и Запад как имен собственных, обозначающих страны и территории, расположенные в восточном и западном направлении, и их страноведческие особенности, возникло сравнительно недавно и не изменило словообразовательную модель.

Существительные западник и восточник, образованные от имен собственных Запад и Восток, в русском языке есть, но они не связаны с наименованием жителей. Западнический — относительное прилагательное, образованное от существительного западник.

Существительное западник (← Запад) — сторонник общественного течения, возникшего в 40–50-е гг. XIX в., представители которого выступали за европейский путь развития России. Современные западники выступают за сближение России с Западом и перестройку российской экономики по западному образцу.

Существительное восточник (← Восток) — специалист, изучающий историю, языки, литературу, культуру, религию, философию, экономику и политику стран Востока.

Слова *востокцы и *востокцкий в русском языке отсутствуют.

Это вполне корректный, хотя и устаревший оборот речи. Вот цитаты из "Национального корпуса русского языка":

Мо́жет быть, в глубине́ души́ импера́тор да́же пожале́л заключённого Конаки и вполне́ удовлетвори́лся ссы́лкою в ка́торжные рабо́ты престу́пной ба́бы-кабатчицы. [Ю. Н. Тынянов. Малолетный Витушишников (1933)]

Съезд выбрал из своего состава самостоятельное правительство «Терский народный совет», под председательством некоего Пашковского, сосланного некогда в каторжные работы за ограбление казначея реального училища и возвращенного) в силу общей амнистии, данной Временным правительством. [А. И. Деникин. Очерки русской смуты. Том II. Борьба генерала Корнилова (1922)]

Да за мои мысли меня бы, может, уж в каторжные работы давно угнали! [И. С. Шмелев. Человек из ресторана (1911)]