Apparently OASTH has added a direct line from Macedonia Airport to the Chalkidiki KTEL. The line's number is 79A, and it's non stop. I'm not sure if the line is only for the summer, it might make sense to send OASTH an email and verify the line will be in service when you plan to arrive in Thessaloniki.
Getting from Thessaloniki to Vourvourou with public transportation is... not a very good idea, the first part of the trip alone is complicated enough.
You'll need to get from the airport to the Chalkidiki KTEL1 station, and that's a small adventure in itself. OASTH2 doesn't have offer a straight route, you'll need to change buses, and the route their website suggests is surprisingly bad. You'll have to go about 15Km in the wrong direction, passing through the city's centre3, to reach the central KTEL station and then either get a KTEL bus for Chalkidiki, or get an OASTH bus for the Chalkidiki KTEL station.
The amazing thing is that the Chalkidiki KTEL station is very close to the airport, they are both at the side of Thessaloniki facing Chalkidiki, while the central KTEL station is at the opposite site. There might be another option, changing buses at the IKEA bus station, but I have absolutely no idea how frequent buses running the two routes (airport - IKEA and IKEA - Chalkidiki KTEL station) are, and even if this route is an option you'll probably have to wait for a while before changing buses. Getting a taxi from the airport is the more sensible choice, it's a 20 - 25 minute drive and it will cost you about 15-20 € (educated guess, and I'm including the extra charge for your baggage).
Once you reach the Chalkidiki KTEL station, you are looking for the next bus to Sithonia. There are buses going straight to Sithonia, but depending on the then schedule it might make more sense to take the Kassandra bus to Nea Moudania, and then change for Sithonia. That's not something to worry about, all you need to do is mention that you want to reach Vourvourou when buying your ticket, they'll let you know what the better option is. KTEL routes are pretty regular and run on time, the buses are all air conditioned and generally clean, and the current fare for Ag. Nikolaos is 11.60 €. It might be a couple of Euros more for Vourvourou.
Finding a rental car in Vourvourou is not impossible, but it's certainly not easy. The settlement is a bit scattered and if you haven't made arrangements prior to getting there, you might find yourself without a car. There are a couple of car rental services but they might not even be open in May. If you don't have the option of making prior arrangements then... your best bet would be Nea Moudania or Nikiti, the two more populous villages of Chalkidiki. The better option depends on how much of Chalkidiki you want to explore, if you only want to explore Sithonia, then Nikiti would be the better option, but if you also want to explore Kassandra, then both options are valid and you might get better prices at Nea Moudania. Also buses from Thessaloniki to Nea Moudania are far more frequent than to other Chalkidiki destinations.
IMHO, the optimal route would be:
- Airport to Chalkidiki KTEL station via taxi,
- Chalkidiki KTEL station to Nea Moudania via KTEL bus,
- Nea Moudania to Vourvourou by car.
Some general tips:
- Routine checks by traffic police are frequent in Chalkidiki, you should have your passport with you.
- Be very careful when driving in Kassandra and Sithonia, there are some low visibility turns that are quite dangerous.
- Greek drivers are a bit antagonistic, and from my experience Chalkidiki drivers are the worst. If someone tries to overtake you, just let them.
1 Intercity public transport bus service.
2 Thessaloniki urban transport organization.
3 And if we are talking middle of the day, the traffic will be horrible.