> I'd be surprised if unbleached brown paper, screwed up as padding, came out worse environmentally than oil derived plastic.
I would not be surprised; the production even of unbleached Kraft paper is quite energy intensive and environmentally bad (look up "black liquor" for example). Oil derived plastics (not very nice either by any stretch of the imagination) appear to use less energy to produce and of course much much less to transport.
> It's probably polythene or variant which doesn't really biodegrade and lasts for centuries. Or leaches chemicals or ends up in the ocean and photodegrades to little bits.
PE doesn't really biodegrade in any meaningful sense of the word. But if stuck in the ground it doesn't release any more carbon into the atmosphere, unlike decaying organic matter. Typical PE film doesn't contain interesting plasticisers so there's nothing to leach out.
The nasty end result of PE film is when it flies about and gets eaten by animals. That's why plastic bags are so horrible. I don't know if these air bags suffer the same fate; I suspect they do. That's bad.
But you said "envoronmentally" not just waste stream: when I look at the total life cycle it's not clear to me that paper is better.
Note that if oil were only involved as feedstock (so both products were produced with only wind or solar electricity) then the calculus could be different.