Tor is correct, there are usually plenty of taxis at the airport to meet incoming flights. However, I can appreciate that if you are arriving early morning you would prefer the security of having something booked.
If you have booked accommodation and have done so direct or through an independent (as opposed to package tour operator) agency they are usually happy to arrange taxis for their guests. Alternatively you could book a taxi through a local tourist office in Paleo. If you post a similar query in the Paleo forum someone will provide contact details for one, I stay elsewhere on the island so I can't help with that.
I hope you get something sorted.