You will need a visa for Turkey, but the other countries you have listed (Greece, Cyprus, Italy and Malta) do not require visas from American citizens. Also remember that Crete is part of Greece, although I don't see it on your map, so perhaps this isn't relevant. A Turkish visa is issued at the border to US passport holders and is good for 3 months of multiple-entry travel.
First of all, Antioch is not in Syria, but rather in Turkey, so you can, in fact, start your journey there. Antakya, as it is known in Turkish, is now served by flights from Istanbul and is well-equipped to handle tourists. Besides the Christian attractions, it has a world-famous mosaic museum and a number of archaeological sites nearby.
From there, you can stop at the other locations using Turkey's bus network. Adana will be a base for you to reach Tarsus and for you to proceed onwards to Konya [Iconium]. Pisidian Antioch is near modern Isparta and Ephesus is near the towns of Selçuk and Kuşadası.
Here's where it gets tricky. You can either try to cover the remaining Turkish locations by travelling north to Ayvalık and Assos and then back south along the Ageaen coast before flying north to Istanbul in order to continue on to Greece. If you do this, then the smart thing would be to have already visited Cyprus since there are ferries from the town of Silifke near Tarsus (see above). The other choice is to remain more faithful to the order that Paul took, in which case you should you can travel from Ephesus to Thessaloniki (via Izmir) to start on the Greek cities, later returning to Turkey.
TURKEY B & AEGEAN
You will need to travel to Assos, which is a tourist town on the north Aegean. Ayvalık is further south and is useful since there are ferries to the island of Lesbos, where you will find Mytilene. Izmir, just south of Ayvalık, also has ferries to the island of Chios (in Turkish, Sakızadası) although you will also be able to travel directly between the two islands. From Izmir, there are very frequent buses that ply the south Aegean coast. Stop at Ephesus again to catch a ferry from Kuşadası to the Greek island of Samos before returning to the mainland for the last few stops. Miletus is probably best visited from Aydın while you can stay directly in Patara. The islands of Kos and Rhodes are served by ferries from Bodrum and Marmaris respectively.
GREECE, ITALY and MALTA
Your trip in mainland Greece should probably start in Thessaloniki, from where you can work your way down south. Athens could be a good place to fly from since there are flights to Cyprus (if you haven't already been), Rome and Malta. You could also fly to all these locations from from Istanbul, although the twice-weekly Air Malta flight always leaves in the middle of the night and goes through Sofia on the outbound leg. If you want emulate Paul's shipwreck on Malta, there are catamaran ferries to Valletta from the town of Pozzalo on Sicily once a day.
I think the biggest decision is whether to split the Turkey part into two separate trips, or visit it, Cyprus, and the Aegean islands in one shot to save time.