I'd avoid Paphos like the plague.
Stopped there in 2007 with a group of planes (all single engine pistons of a similar weight but some N-reg and some G-reg) and they gave us a very difficult time with flight plans and charged each of us very different fees - appeared to be based on what they could extort out of us individually rather than according to a standard charging schedule.
We skipped our planned stop there on the return trip and will never route through there again.