I thought I'd update this with my experience.
I rented through Elephant Rentacar in the end.
For 11 days' hire in November (2015) I paid EUR161. For this I got a Mondeo-sized car (Chevrolet, I think) with aircon. I had to pay EUR 45 for a half-tank of fuel. Given an assumed 50-litre tank, this was a little over the rate at the time but not obscenely so and much better than all the major brands at Paphos airport. If it was a 60-litre tank then it was probably almost the market rate.
I'd also say that it was a stress-free experience renting from them. The car had a few dints when I picked it up that were not marked onthe hire sheet (it was dark when we collected the car) but I called to discuss these and was told not to worry about them. True to their word, they did not seem to check the car upon its return, other than it was in a decent state.
It seems like they are genuine good guys, but that's just my thoughts.
I was driving all over the island so I could plan to return it with a little bit of fuel in it. Ok, so I lost out a little there but the fairly low cost or hiring a car for 11 days seems a good tradeoff for a loss of 5 litres or so.
I would rent from them again.