Hah. I’m glad to see I’m not the only one with “Paul Molitor.” The apostle was also in my head, so that rounds up the top three for me. #4 is Paul Reubens. Why these sprang to my head before either Paul Simon the songwriter or the senator (I’m an Illinoisan) is beyond me.
Paul the Simon Pegg alien. Asked the other half and that was his response too. And I know why - that was a GREAT movie! 
Me.
Pierce. I don’t why he came up first.
Well, it should be my dad, but it’s McCartney.
Even before Paul Newman, who I adore[d].
The Apostle. If you meant a different Paul, you’d have used a last name, wouldn’t you?
Paul Simon.
McCartney
McCartney, followed by Simon, Lynde, the apostle, and the fish stick lady.
Yes he was, twice as I remember. I like the second one the best.
So, Paulrus?
My brain went “McCartney - Rudd” in that order.
McCartney, followed by Newman.
The Apostle, followed immediately by Maud’dib.
I can’t believe I’m the only one.
First one I thought of was Paul Stookey, of Peter, Paul and Mary. Second was Paul Simon.
Me! For 'tis my name.
After that I thought of the movie with Simon Pegg and Nick Frost.
Paul was a very common name when I was born. Now it’s very rare in the English-speaking world.
Saul aka Paul. Then Beatles.
I just thought of one I haven’t seen mentioned yet: Paul Winchell of Jerry Mahoney fame.
And there’s also Rodriguez.
The Man Formerly Known as Saul.
Another with McCartney as the first.
He was the second for me, but mostly because I saw this thread while on a Simon Pegg bender.