Paul writes about and to, places in the areas of Greece, Macedonia, Asia Minor as well as Illyricum.
While not impossible that a Jewish man from the Levant would and or could travel to these places in the 1st century as part of a missionary expedition, it seems less likely to me than having his presence explained by his having been part of the civil wars of Rome there from the mid to late 1st century BCE. Further, two of the places that he writes to (Thessalonica and Philippi) are centered around the area of Philippi where the battle between the forces of Cassius and Brutus against the armies of Mark Anthony and Octavian took place during the Liberator's war of 43-42 BCE.
Philippi would become a Roman military veteran settlement colony after this war as will Troas, being settled by veterans of Augustus, as Corinth and Sinope were under Julius Caesar not much earlier.
Paul does not write to Damascus, Jerusalem, Syria or Cilicia (that we know of) and only mentions them in his letters as places that he has been in the past.
Paul does write to people in the city of Rome but it is clear that he has never been there. Also in that letter he states his intention of first taking monies collected from Greece and Macedonia to Jerusalem and then visiting them on his way to Spain as he hopes that they will assist him in this endeavor.
It is interesting to note that Spain will be the last place that needs to be pacified by Augustus at the end of the Roman civil wars of the late Republic as well as having quite a few settlement colonies of Julius and Augustus Caesar there.
Paul being in Illyricum in the 1st century seems problematic but as there were major military bases there in the 1st century BCE leading up to Julius Caesar's planned invasion of Parthia before his assassination by the Liberators, Cassius and Brutus, It seems more likely that after the Philippi battle that the losers would be marched there to sort everyone out. Pure speculation of course but possible.
It should also be noted that the cities that he mentions that were not veteran colonies (Athens, Ephesus and Antioch) were areas that had major concentrations of Roman military in the 1st century BCE. Especially under Mark Antony.
I always found it odd that cities like Smyrna, Pergamon and Pella are never mentioned even though they are much more important cities than towns like Philippi and Troas. But then there were no troop concentrations in Smyrna, Pergamon and Pella in the 1st century BCE.
He never mentioned Tarsus either, which would seem odd if he were from there, but not so odd when one realizes that it also had no troops stationed there. The same holds true with other major centers like Mytilene, Cyzicus, Nicea, and Nicomedia which were all bigger and more important than Thessalonica except that they held no troop concentrations while Thessalonica was the main port for overland Roman troop movement at that time.
So that Laddies and Germs is the kernel of my thesis.
I contend that Paul is up in Greece, Macedonia, and Asia Minor as a militant in at least the battle of Philippi and is attached to the Liberator's army, probably as an axillary, possibly recruited in Syria or Cilicia and afterwards (being a non Roman on the losing side and not part of a regular army) found himself stranded in Greece or Macedonia with no way to finance his way back home.
I further contend that he had a background in a sectarian messiah cult, probably centered around Damascus and Jerusalem, that he used to create his own version to earn a living where he now found himself.
I will close with this...
500 men would be the size of a normal Roman military axillary unit.Now, brothers, I want to remind you of the gospel I preached to you, which you received and on which you have taken your stand. By this gospel you are saved, if you hold firmly to the word I preached to you. Otherwise, you have believed in vain.
For what I received I passed on to you as of first importance: that Christ died for our sins according to the Scriptures, that he was buried, that he was raised on the third day according to the Scriptures, and that he appeared to Cephas, and then to the Twelve. After that, he appeared to more than five hundred of the brothers at the same time, most of whom are still living, though some have fallen asleep. Then he appeared to James, then to all the apostles, and last of all he appeared to me also, as to one abnormally born.