Just a quick update that may be useful to others: the complete error message I was receiving had nothing to do with Windows 11 (although it is terrible nevertheless), because I had Win10 machines on the same network unable to add the printer with the same message containing: "No more connections can be made to this remote computer." The issue only affected computers that did not have the printer added a while back, i.e., those that already had it installed could print a test page.
Anyway, the problem seems to be some silliness on the server side. One solution is to enable SMB1 on the NAS side. I am guessing that it either removes the limit on the number of connections, or clears some sort of cache when it restarts the file service for SMB1 to get enabled. For a Synology DSM, it is in Control Panel > File Services > Advanced Settings. SMB1 will need to be enabled on the client ("turn windows features on or off" in Windows).
I think this could be marked as solved.
