Fruit and vegetables are manageable by bringing ones own bags, providing products aren't prepacked. However, even in states (and supermarkets) where single use bags are banned, the single use fruit and veg bags are still on offer and seem to be widely used.
Cellophane bags and packaging are an option for prepackaging.
(You can tell if the "plastic" used in packaging is cellophane or plastic quite simply: cellophane burns like paper; plastic blisters, bubbles or melts). Cellophane is a plant-based product and can be composted.
Some other products currently wrapped in plastic could be wrapped in cellophane too (toilet paper, frozen vegetables, cheeses etc.)
We are going to have to phase out plastics altogether if we are serious about:
1. keeping to 1.5˚C (or even 2˚C) of global warming
2. managing when oil gets too expensive/scarce
3. trying to rehabilitate the oceans and the critters who live there
Even recycling plastics (and other materials) uses large amounts of energy in transport and processing so recyclable plastics are not the answer.