On my side I did only this steps:
- delete the Users/[your user name]/Library/Application support/BraveSoftware folder
- relaunch Brave
and it worked.
I didn’t uninstall Brave, nor downloaded it from Github.
The BraveSoftware folder is recreated when Brave is started, but does not prevent Brave to start anymore.
(You may need to enable the display of the Library folder in Finder layout menu.)