The Microsoft Installer (*.msi) format supports what you want do to, unfortunately Visual Studio only offers limited customisation and is designed to be used for basic projects.
There are a lot of resources out there on this topic and many other people asking similar questions. My best advice would be spent some time researching the MSDN documentation.
...
Update
OK. After spending 30 minutes reading a few articles, I think it may be possible using a custom action that you package with your new installer.
Follow this MSDN article on creating a Custom Action. It involves creating a new class library, adding an System.Configuration.Install.Installer
class, adding it as an output to the setup project, and then selecting it as a custom action.
To view your custom actions tab, right-click on the setup project and select View > Custom Actions.
From here: you will need to write the code to remove the installation directory and AppData profile. This article on how to set Custom Action Data may be helpful.
Good luck.
HTH,
Dennis