Hi Hummerman,
I stayed in Protoras when I went to Cyprus, and had some cracking birds on a hillside behind my hotel, showing you really dont have to go far. Any area of scrub or non built up areas can yield anything, I had 1000+ Honey Buzzard, Olive Tree Warbler, Crezchmars and Ortolan Bunting, Quail and loads of other bits within 500m of the hotel!! Nearby birding sites are Paralimni Lake and Cape Greco, Paralimni's good for crakes and waders, Cape Greco for Eleonora's Falcon. A quick wander down to the fields near the beach in Protoras can also be good too, had some good stuff down there such as Citrine Wag. Good luck, I think the key is just to spend some time at local unbuilt up areas.
Cheers