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

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

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

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

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

Корректно без притяжательного местоимения: чайки расправляют крылья в небесах.