I found a 2. cent BCE
Roman general by that name:
Lucius Aemilius Paulus
http://en.wikipedia.org/wiki/Perseus_of_Macedonia
(here spelt with double L for whatever reason)
I guess Paulus was a fairly common byname in ancient Rome.
In the case of the biblical author
Paul we do not know whether he himself chose that name to correspond to his Jewish name
Saul or maybe his parents.