Newspaper is a good alternative to anti-static bags if you don't have any laying around. If the seller has it wrapped good and protected well from bouncing around, I think you will be ok.
The fact that the seller, from eBay, immediately warned you may point out that they already damaged the CPU and are trying to sell it, then blame the damage on the shipping or the way you handled it. This seems of something typical an eBay seller would do, especially if they have very few reviews.
I don't think the shipping itself is going to ruin the CPU, and you taking it out of the box shouldn't hurt it either. The only way you will cause damage is if you're purposely rubbing your hands along some nylon, trying to create enough electricity to run your home. Or if you happen to break out your Van de Graaff generator or Tesla coils, you could cause some problems there too.
I've heard that ESD damage can be slow and gradual, but I've never handled any parts while using an anti-static strap, etc. In my opinion if it's ESD damaged, it won't work from the start.