....or Beirut, which is what I did in a 172 from Larnaca when I was last there late '90's (about 110NM direct-ish track if I remember correct).
As prevously mentioned, FPL required for all flights, and flying on the Greek side was limited to a couple of pre-defined routes, running roughly W-E from Paphos to Larnaca.
This was a while ago, so might have all changed (become more relaxed) though.