I don't think TM always works well with multiple Macs sharing the same TM space. My guess is that one of them has eaten up the bulk of the available space for its backup and the new backup on another needs more space than the free space available. Yes, it should delete oldest files on its share of the space but maybe one of the Macs has- over time- eaten up so much space such that even with usual TM "oldest" deletions, there is not enough space for new backups of the specific Mac wanting to backup.
You might check to see how much of total space is "owned" by each Mac compared to how much total space you've allocated on that Synology. You might find that you have to delete the hog's TM backup, let the Mac trying to backup now do its backup in the (probably considerably) freed up space and then fresh backup the Mac backup you just deleted.
In other words, if total space you allocated on Synology was, say, 4TB, and one Mac has piled up enough history to "own" 3.6TB, the balance of only 400GB may not be enough for fresh backups for the other Mac trying to backup now. It's call for space probably can't deal with other Macs backup but only its own... and perhaps whatever it holds in that 400GB is not enough to reduce in the TM "oldest" files way to create sufficient space for updated files.
The analogy would be having a DAS drive attached on which you've added 3.6TB of other files and are trying to TM backup to only the 400GB that remains.
If you don't discover that one has gobbled up most of the space, you might have to wipe the whole TM space on Synology and then fresh backup each Mac again (basically start over with clean backups). However, if the above guess is right, you'll likely eventually fill up enough to get this problem again.
Another way to potentially address this is expand the allocation of space to TM on Synology to make the overall space larger. For example, if you've given it 4TB, expand it to 6TB to add 2TBs of fresh space to the overall pool. Then let the current Mac backup and that should work. I don't completely remember that adding space to Synology TM pool is possible without fresh backups after the expansion, but I believe it is. This should do the trick too.