I do remember a supermarket (DIA) in Grado, right next to the camino, at the end of town, a bit before Autobar hotel. And according to googlemaps, there is also a Coviran supermarket a bit further ahead, on the main road out of Grado, still on the Camino.
In Cornellana there is a small grocery store between the Monastery-albergue and the center of town. Then in Salas there is also at least a DIA supermarket, but probably one or two other stores in town. In La Espina there is the small gorcery store under the donativo Albergue El Cruce. In Tineo there must be one or two supermarkets as well, although not at the Camino.
In Campiello, Albergue Casa Ricardo has a grocery store in the bar right opposite the albergue. In Berducedo there is also a small family grocery store behind the public albergue.
In Grandas I can't remember any stores, but since it is a fairly "big" town, I'm sure there must be one or two at least. The same in A Fonsagrada.
I think it is not hard to self-cater for a veggie on the Primitivo (maybe not that easy for a strict vegan).