historically, the first guy named Paul was saint Paul / Saul of Tarsus.

his original name was Saul (presumably King Saul, jewish 1st king, 1000 years before him.. both from Benjamin tribe iirc.)

his nickname was Paul, historian assume he already had that nickname before road to emaus event, most likely because Saul was a popular name... and Paul seems like Saul (jewish word) being romanized.. like Jehoshua became Jesu or Jesus in greek documents.

He then decided to use Paul as his pen-name and everyday-name after his convertion because:

• to make clear distiction with his past

• he became an international guy, travelling everywhere, and a romanized name would be easier to use.

but yes, the use of name Paul, most likely, originated from him.