Background
Anydesk is a legitimate program. I use it to help my family members with their computer problems. It is unfortunate that scammers use it too to access the victim's computer. They usually tell you what to do to install Anydesk in your computer. Without Anydesk or something similar, they do not have access to your computer. Once you install Anydesk and allow them to gain full full control of your computer, they may install other programs and malware without your knowledge. There are quite a few videos on YouTube that shows how the scammers operate. Here is another one.
From your edits it looks like you have not uninstalled it. you may have removed the icon from the dock, but that does not remove the software. Since it is not clear how you installed it in the first place, I will tell you a few methods.
Warning
The scammers may have installed other malware once they had access to your computer using Anydesk. Malware includes other software to regain control of your computer, keyloggers, to record and steal your passwords, to name a few things. For this reason, as others have said in comments and answers, it is best to reformat the hard drive and reinstall Ubuntu.
1. Uninstall using apt
Open a terminal by pressing Ctrl+Alt+T. Enter the command:
sudo apt purge anydesk
Note, apt purge
uninstalls the app, as well as removes all the configuration files
If this does not work and you get see something like:
E: Unable to locate package anydesk
Then Anydesk was probably not installed using the "deb" file or the PPA.
Clean up
Once Anydesk is removed by this method, you may want to remove its repository, GPG key and folders.
First find the repository and GPG files:
sudo ls /etc/apt/*/anydesk*
You will see an output like this:
/etc/apt/trusted.gpg.d/anydesk.gpg~
/etc/apt/trusted.gpg.d/anydesk.gpg
/etc/apt/sources.list.d/anydesk-stable.list
2. Uninstall using GUI
This method does the same thing as the command line method above. So, if the above didn't work, this probably won't. Unfortunately the Ubuntu Software app does not find Anydesk when it is installed. So there is no easy GUI method to uninstall it without installing another software like gnome-software
or synaptic
.
One way to get around it is to right click on the downloaded Deb file:

and select Open with other application. Then select Software Install:

This will open Ubuntu Software to the following page:

Click on the red trash can to uninstall confirmation dialog:

You will have to provide your password to uninstall Anydesk. Once uninstalled the red icon on the top right hand corner will be gone. You will still need to delete the config folders Anydesk created as default, and in your home folder. These are easier to delete from the terminal:
sudo rm -r /etc/anydesk
See the Clean up personal files section below for the rest of the folders to delete.
If you installed Anydesk from the PPA repository (from the terminal) then you can use the app software & Updates. You will find the Anydesk PPA repository under the Other Software tab:

Use the Remove button below to remove it.
They you will have to remove the GPG public key for Anydesk. To do this go to the Authentication tab of the software & Updates app and look for "philndro Software":

Use the Remove button below to remove it.
3. Other possible ways to uninstall
I am listing both Snap and Flatpak uninstall methods here. I am not sure if Anydesk is available in the snap and flatpak formats. So these may not work. Use the commands:
sudo snap remove anydesk
sudo flatpak uninstall --delete-data anydesk
If these do not work try these commands without sudo
in case Anydesk was installed just for your user:
snap remove anydesk
flatpak uninstall --delete-data anydesk
Even if these commands don't work, they should not harm your system.
Clean up personal files
Then remove these files using the following commands:
sudo rm /etc/apt/sources.list.d/anydesk-stable.list
sudo rm /etc/apt/trusted.gpg.d/anydesk.gpg
sudo rm /etc/apt/trusted.gpg.d/anydesk.gpg~
Now remove all the files in your personal home folder:
rm -r .anydesk
rm -r video/AnyDesk
rm -r Documents/AnyDesk
I think that's all of them.
Hope this helps