Your options include:

Blockchain.info has added the ability to use Barclay's Pingit to buy bitcoins using GBP:
 - https://blockchain.info/wallet/deposit-pingit

And they now also provide Instant online bank transfer in the UK (and Austria, Belgium, Germany, Italy, Netherlands, Poland, Spain, Switzerland):
 - https://blockchain.info/wallet/deposit-bank-transfer

Bitcoin-Central has launched its BTC/GBP market, where you can trade after transferring pounds sterling to their bank in France.  The order book is pretty thin yet but they did just launch:
 - https://bitcoin-central.net/order_book?currency=GBP

You can also send cash (GBP) in the mail to Bitcoin Nordic (in Denmark):
 - http://www.BitcoinNordic.com

And, or course, there may be a chance for a local trade:
 - http://www.LocalBitcoins.com
or
 - http://www.Bitcoin-otc.com

As far as PayPal, about the only option through an exchange would be VirWoX.  With VirWoX you purchase Second Life Lindens (SLL) using PayPal, then trade those SLLs for BTCs.  It isn't the cheapest method, but PayPal beggars can't be choosers.
 - http://www.VirWoX.com