Common misapprehension. He didn’t change his name. Saul and Paul are two different versions of the same name: Saul is the Hebrew version and Paul is the Latin version. So he was Saul to the Jews and Paul to the Romans.
Paul the Apostle, then McCartney
Since I am at this very moment eating some lunch I acquired from here, that’s my first thought.
Then I thought of the stupid Pegg-Frost film.
Then McCartney.
Then Paul and Storm.
Me. But I’m just self-centered that way.
<Awaits around round of “Hal isn’t your real name?” posts>
Paul of Tarsus, then the alien from the eponymously named movie, then Sir Paul McCartney.
McCartney
McCartney, followed closely by Williams.
McCartney, then myself. What can I say.
The All-Paul team, according to Wikipedia:
Anka
Butterfield blues singer
Cezanne
Dirac
Erdos
Francis Webster movie lyricist
Gauguin
Hindemith
I of Russia
Jones singer (Manfred Mann)
Krugman
Levitz
McCartney
Newman
of Tarsus
Pierce
Q. Kolderie record producer/engineer
Robeson
Simon
the Apostle
Urloviz New Zealand footballer
V Pope
Weller British musician (The Style Council)
X. Kelley US Marine Corps general
Young British singer
Zinman
Paul McCartney
Les Paul
Saint Paul
Paul Newman
Rupaul
Paula Zahn
Paul Pascal
Paul Peter Porges
Wow, I wonder who that is?
McCartney automatically. The other ones, I have to deliberately think it over.
My ex-husband. Ugh, thanks for reminding me. 
Peter, Paul and Mary (Paul Stookey)
Without reading the thread first, my brain immediately came up with Les Paul. And there is absolutely no reason why it should.