[SOLVED! For me, anyway]
@Kaelonius is right, but I had to use more than one command to fix whatever may have been borked by the GUI.
This fixed the authentication failure (overkill with privs all, but I wanted my last remaining user to have all anyway, so continue and bear with me):
sudo /System/Library/CoreServices/RemoteManagement/ARDAgent.app/Contents/Resources/kickstart -configure -access -on -allowAccessFor -allUsers -privs -all
After that worked and I could actually not just add the new Sonoma iMac but also connect and control it with all users, this then removed privs for each user to be removed (replace user1,user2... with a comma-separated, no-space list of relevant users):
sudo /System/Library/CoreServices/RemoteManagement/ARDAgent.app/Contents/Resources/kickstart -configure -users user1,user2... -access -off -privs -none
Then, once privs were gone for all but the one user, this command allows access only for the one user left with privs (all in my case):
sudo /System/Library/CoreServices/RemoteManagement/ARDAgent.app/Contents/Resources/kickstart -configure -allowAccessFor -specifiedUsers
Finally, and good grief! I can now control this one remotely and as intended.
NOTE: Can we please stop the unquestioned annual macOS releases and forced 3-year EOL and get back to responsible and less bug-prone development, even if a little slower, please?