Unfortunately that's a bad (but rare) bug in macOS and hard to fix. The database is probably corrupted and needs to be deleted, but the problem is that the database is under "System Integrity Protection", thus a normal user can not delete it.
Before trying the steps below, first try whether these terminal commands fix your issue:
sudo tccutil reset All
sudo tccutil reset Accessibility
These would be the necessary steps, but they are not really easy...
1.) Disable SIP (system integrity protection). Which is a complicated process unfortunately (see https://apple.stackexchange.com/a/208481 ). Afterwards restart & boot back into normal macOS
2.) Delete/rename the tcc.db file (e.g. using this command: sudo mv /Library/Application\ Support/com.apple.TCC/TCC.db /Library/Application\ Support/com.apple.TCC/TCC_old_backup.db )
3.) Boot into Recovery Mode Again
4.) Enable system integrity protection again (command: csrutil enable )
5.) Reboot the Mac