Time Machine stopped recognising backups on the NAS storage and does not make new backups anymore
So it seems that the problem is related to my router or one of the recent MacOS upgrades that probably introduced something new or broke compatibility because just weeks ago it worked properly. Just for the record the model of my router is Keenetic Giga.
How did I understand it? I created a blank HFS+ partition, connected my HDD to the router and fed it up to Time Machine. I got the same error as described in my question. So it is clear that the cause of the error is not associated with the backup itself.
So I decided to migrate all my backups to a new partition on that drive and use it as a local backup storage instead of NAS. And because I had that .sparsebundle file I needed to figure out a way to &quot;burn&quot; it (copy its contents) to the new APFS volume. It seemed like an easy task to do but it's really not...
I'll skip a story with all my tries and failures and move directly to the solution.
So to convert a .sparsebundle file to APFS volume there is a feature called &quot;Restore&quot; in the Disk Utility. But UI is not much helpful because in general this functionality sucks when it comes to the .sparsebundle format. So we need to arm ourselves with patience and Terminal. And at first we need to mount the &quot;.sparsebundle&quot; image through Finder and then change metadata of the mounted volume a little:
diskutil apfs changeVolumeRole /dev/diskXsY t
where diskXsY - is the identifier of your volume which you can find running diskutil apfs list

This command will change the role of your volume and MacOS will no longer know that it is a backup storage. Without doing it the next command will fail (due to a bug).
sudo asr restore --source /Volumes/EXTERNAL_HDD/{the name of your computer}.sparsebundle --noverify  --target /dev/diskAsB --erase  --debug --verbose
where /dev/diskAsB is the identifier of a volume that you want to use as the backup storage. 
--noverify is needed here because there is also another bug in this utility.

After you enter a password (if you have an encrypted backup) and agree to erase the volume this command will replicate the contents of your &quot;.sparsebundle&quot; onto the target volume. It will take a while...
After it finishes you will almost receive a functional (unencrypted) backup storage. To make it fully functional you should run:
diskutil apfs changeVolumeRole /dev/diskAsB T

This command will assign a Backup role to your target volume and Time Machine will recognize it.
Later you may want to encrypt your storage with &quot;hdiutil&quot; (warning: it will take hours to complete).
At this stage I configured Time Machine to use the drive as a local backup storage and after doing that one of the folders changed its suffix in the name from .inprogress to .interrupted.
At the end of the day Time Machine copied an increment only and it looked like this:


After the backup process finished I looked into the contents of the drive and found out that Time Machine killed my old backups and during the Cleaning up phase it went from this:
$ ... % ls
2021-05-06-201324.previous  2021-05-22-195414.inprogress
2021-05-06-212814.interrupted   backup_manifest.plist

to this:
$ ... % ls
2021-05-22-212814.previous  backup_manifest.plist

I believe that it is due to the interrupted backup which you can see above but I don't want to spend any more time on that. So technically I still didn't get my old backups back and all I got was pain from multiple Apple bugs and inconveniences but at least I have more knowledge now how it is built under the hood and probably this information will be useful for someone who want to convert .sparsebundle to APFS (or to be more concise - to a local backup disk formatted as APFS).