unable to open /var/db/sudo/ts/<username>: Permission denied

That’s a very odd failure. I would probably boot to internet recovery and reinstall the os on top of what you have. If you have a backup, great and if not this isn’t a risky operation and something is certainly messed up with the permissions and sudo failures.

Unless you have a very good idea why things are specifically broken, perhaps some scripts to change ownership or other sorts of administrative changes that you know were made to that system, it’s probably a lot faster to just get a get operating system and then fix any remaining problems every install doesn’t solve immediately.

As confirmed by OP...

the user profile might be compromised.

Create new user and try following (hopefully without Permission errors).

sudo mv /usr/local/Homebrew /usr/local/Homebrew.old

sudo mv /usr/local/Homebrew.old /tmp