In the eyes of the law, you and the newsagent, who was at the time being represented by one of their authorised personnel, entered into a legally binding contract, especially as you have made a payment as well.
You could argue that any special conditions, terms and conditions should have declared at the time of the transaction, including any policy to decline any adverts.
If you took your case to the small claims court, you would have a very high chance of success, and therefore could claim for the cost of the advert, any potential loss of income (although you would need to clearly demostrate how much) and your court costs. Not to mention the chance of ensuring that your advert isn't discriminated again.
It all depends if you can be bothered for £4. I would just to get one over on him !!