Quick answer: you can do this at the Bank of Cyprus opposite the main post office, at least until the end of 2008.
Long and rambling answer:
Euros have been the currency in Cyprus since 1st January 2008.
Prior to that, the currency was Cyprus pounds.
There were detailed instructions about the changeover, and free currency calculators distributed by banks and supermarkets.
It all seems to have gone fairly smoothly, although prices have undoubtedly increased. Moreover, the euro has become strong while both sterling and US dollars have grown weaker, thus those of us whose income is from the UK and/or USA have seen it reduced somewhat.
Still, going into the euro was a positive move for Cyprus overall, and we're just about getting used to it. We used up our Cyprus pounds in January, then as we discovered odd notes and coins around the house, we were able to exchange them at the local bank. We did keep a few small coins for posterity (I wonder if posterity will be interested in them?) but the rest have gone.
Then, in the summer, we had a meal with some friends who still had some Cyprus pounds left from their visit to us a year before. It was a little over £50 (CYP). They gave it to us, since it was no longer any use to them.
A couple of weeks after we returned in August, I was in our bank for something else, and asked if they would exchange Cyprus pounds.
No, alas, the man on the till told me. Only until the end of June. However, I could do it in the big bank in Nicosia, or the bank by the main post office.
His English wasn't too clear, and I was in a hurry, so I didn't write it down or push for details. Surely, I thought, I could find out online.
No. I found several sites telling me that I could exchange my Cyprus pounds at the central bank of Cyprus in Nicosia. But nowhere could I find reference to exchanging them in Larnaka.
However, today I had to go to the main post office to collect a parcel. So I picked up the Cyprus pounds which were sitting in my desk, just in case.
I noticed several large banks on the corner opposite the post office. But I decided to go into the Bank of Cyprus first, since that's the bank we use (albeit not our branch) and I didn't know if an account was needed.
It was much bigger than I had expected. And there didn't seem to be anywhere obvious to queue. So I hung about until a cashier was available, and then went to ask him if it was possible to exchange Cyprus pounds.
'Yes, of course!' he said, and pulled open a drawer full of Cyprus pounds. 'What do you want?' he continued. 'Dollars are good! But maybe you want euros?'
I agreed that I wanted euros. So he calculated the exchange on the computer: it came to €95.68.
Then - since this IS Cyprus - he gave me €95.70.