ossigeno

Resident in Australia. Have some UK paper share certificates I would like to sell.

Share registrar tells me I need a share broker or bank than is licensed to trade in both UK & Australia.

Any recommendations?

Kiwipaul

Incorrect. If you still have a bank a/c in the UK contact their share dealing section and ask them to sell them for you and pay the money into your UK a/c.
If you do it via an Oz broker then yes they need to be licensed in both countries.
You might be able to find a UK online broker that will sell them for you it depends on the value of the stock. Most brokers won't be interested in a small amount especially if it's just a one off.
When I had UK shares I let Killik & Co handle my transactions, but that was 10 years ago.

Brisbannite

When you sell your shares remember to declare it in your tax return. You'll need to work out what they were worth when you entered Australia and pay tax on the difference between that date and their value on the date your sell them. Don't forget to factor in the exchange rate for both of the dates. If you're in luck fluctuations in exchange rates will be in your favour.