I have seen paper bags that have a plastic inner coating which I guess they spray on. But that seems to be skirting around the rules, as the objective is to eliminate plastic in packaging.But buying plastic bags to put stuff in kind of defeats the purpose too.
My local pak n save had no plastic bags or paper bags for the fruit and veges when I went in yesterday. I guess they now expect people to bring their own packing. Considering how filthy trolleys can be, I wouldn't want to be putting naked fruit in contact with them.