2 points.
1) Sellers charging PayPal fees to buyers is against eBay policy.
2) Sellers are permitted to charge a packaging and handling fee within reason. If fees were stated upfront then the postage paid is irrelevant.
So the seller seems wrong in one aspect, but right in the other. I wouldn't recomend leaving negative feedback for him, though you may want to report to ebay for the PayPal fee abuse.
-edit-
Just a quick note. Even if it was mailed in a cheap paper bag, sellers are permitetd to still charge a handling fee. Most companies outside do this anyhow, and most don't blink an eye. Ebay is just a little more intimate.