As a Jew, he had a Hebrew name - Saul. As a Roman (a citizen of no mean city ...) he had a Latin name - Paul. They look and no doubt sounded pretty similar so would have been an easy choice.
Paul could equally have been a nickname, based on his Hebrew name and very relevant for a physically small man.
My Jewish friends today usually go for a Hebrew name with the same initial as their English names - Denis is David for liturgical purposes, Jackie is Yael, Penny is Pnina. But, Anne and Myrna are Chana and Miriam, using the original forms! It seems to be a pleasantly relaxed system.