without demand from modern-day vegan consumers
No, they weren't.
I grew up in Bulgaria, and these products are entirely new. They appeared basically at the same time as they started becoming common in supermarkets in Western Europe, so after 2015 or so. I'm quite certain that my grandmother or mother wouldn't know what they are even if I tried explaining them.
Some somewhat related products have been around for longer, but never as a local delicacy.
- Tofu might have become available with the first Western supermarket chains in the early 2000s, although these took until the end of the decade to get a decent market share, so most of the population may never have noticed it in the beginning. Today, it's recognizable, but regarded as an exotic import.
- Manufacturers in the 90s started using large amounts of vegetable fat (and I suppose other kinds of plant-derived matter) when making standard kinds of cheese. This was a cost-cutting measure, the flavor was intended to mimic all-dairy cheese, the product was not vegan or suitable for people with dairy alergies, and when the news outlets made a point of reporting about this, the labeling laws were changed. In that sense, there used to be a common cheese-like product containing a lot of plant matter, but not as a food in its own right, but rather as an imitation product which the public considered a deceptive practice.
- Traditionally, any use of non-cultured cream was rare in Bulgaria. In the 90s, stores started carrying liquid "cream" which was in fact a non-dairy substitute that kinda works like half-and-half in sauces. This remained the only kind of "cream" available for a long time. As late as 2018, I knew of exactly one supermarket chain in Sofia which carried exactly one (imported) brand of real dairy cream. So the substitute product is still very common, but not as a local delicacy, but rather because people don't even realize that the "cream" they read about in Western recipes is supposed to be dairy-based.
Nuts and legumes are widely eaten in Bulgaria, including some uses which aren't widespread in the West (e.g. dry roasted chickpeas as a snack), but I have never encountered anybody processing them into a nut milk, much less curdling them.
As others have said, the labeling on these products has nothing to do with local food customs. Rather, the producers wanted to provide a dairy-free imitation of the dairy cheese that Western customers know under the moniker "Balkan style" or "Greek style", so they put that name on the packaging.