Ohne Umsteigen geht es nicht.
Du kannst von Protaras über Ayia Napa / Larnaca Airport bis Limassol (= Lemesos) fahren.
Dort steigst du um in einen Bus nach Paphos.
Das ist m. E. die kürzeste Verbindung.
Vorher sich bei den Busbahnhöfen erkundigen, ob die Busse auch fahren. Das ist nämlich nicht immer der Fall. Kritisch sind vor allem die Wochenenden.
Außerdem: Da es sich um unterschiedliche Busunternehmen handelt, kann es schon mal sein, dass du recht lange auf den Anschlussbus warten musst.
Wenn du meine Meinung dazu hören möchtest : Das könnte ein ziemliches Rumgegurke werden. Ich würde an eurer Stelle für 2 Tage einen Mietwagen nehmen.
In Paphos ist der Busbahnhof übrigens oben in Ktima Paphos (der Neustadt) - allerdings nicht dort, wo die städtischen Busse halten (am Markt), sondern von dort aus ein Stück geradeaus in die Gassen hinein bis zum Karavella Platz.