there's an office in Paphos called Tony's, down the side of Papantonios supper market in town, right net to the lights, they have the passport forms, once filled in you can either take it back to them and they will do all the leg work for you, (at a cost, but well worth it) or you can take it to the Brit High commission yourself. We let Tony do ours last year, no problem had the new passports back in about 10 days.