Try:
sudo apt remove brave-browser
Then check if you have only One Option for Brave-browser in the app menu.
I am a bit bewildered, too, actually. I used to use Brave Browser and installed it in much the same way as the guide I linked you to above. I never installed Brave from the Software Store.
And it set as default just fine.