is there a danger that I can brick the tablet?

Yes but it sounds like it's all but unusable as it is. Have you tried Odin? Do you have a Windows PC to run it on? That might be the safest way to start and if something goes wrong with the recovery method Odin is your most likely safety net. You can also use your recover to make a backup but it will be infected. if you have a decent custom recovery already loaded, you should be pretty safe with a stock rom (as I linked above) or another popular well proven ROM from XDA. Just don't get ROMs from sketchy sources and make certain any ROM is FOR YOUR EXACT TABLET before you try to install it.

First time I am doing this. Looks hard at first sight. Unfortunately I don't have an SD card right now. Does it have any importance where I copy the new ROM on the internal file system?

The internal ROM zip file should probably be copied to /storage/emulated/0 but the safest bet is to boot into your recovery, go to "Install" (or similar) and see what it opens for the default path. You may also have USB file access even within the recovery saving you from having to run your infected OS. So while you're in the recovery see if your tablet shows up on your PC. With some recoveries it's an option you may have to enable. Your tablet may also support USB-OTG if you have any micro USB thumb drives or an OTG adapter.

Read up on XDA for your particular tablet if you're not comfortable doing it. How did the custom recovery get installed or did it come with it? If you have TWRP, PhilZ, or possibly CWM, and your tablet is unlocked, this should be fairly easy.

I did not install anything on it, I got it this way. I don't know what the previous user did to it. All this stuff is new to me. Right now I am trying to download a ROM for it as a first step. I think I also miss some basic knowledge about this because I can hardly keep up googleing the words you use :-)

I think you might want to find someone to help you that is familiar with rooting android devices. How did you restore it back to factory defaults? Just under Settings? And that process worked... when it restarted you had to go through all the set up screens and it still had the virus?

Also, what country are you in? That stock ROM is only for the UK, Netherlands and France (there are 3 different ROMs--one for each country).

No, I wrote it in my question, I booted into recovery mode and - wipe data/factory reset. As soon as the tablet connected to Wi-Fi, it started to live its own life..

I figured that out that I need the XEH, now I am struggling to find a working mirror for it. I blew my chance at samsung-updates.com/device/?id=GT-N8010, I have to wait 2 hours to be able to start a download again.

Is it the stock Samsung recovery? Or does it say TWRM, CWM, PhilZ, etc?

And are you in the UK, Netherlands or France? Did you try this procedure? forum.xda-developers.com/galaxy-note-10-1/general/…

imageshack.com/i/p8c3l2k0j

I am am from none of those countries. I am reading that right now

The solution below Zaheer is another option. It would appear the N8010 is not all that popular of a tablet.

The new ROM seems as a cleaner solution to me than rooting. Also I have installed CM security before and it wasn't that good.

Well hopefully you can make one of the options work. Unfortunately Samsung devices have many differences and what works on one might not work on another. Your best bet is make the Samsung/Odin/Kies solution work. Failing that, you need to find a ROM that works for your tablet and your country. And if it's not a stock ROM be prepared for some things that don't work right (like the camera, GPS, etc.) and a very different experience than Samsung's TouchWhiz.

Is there a way to make sure to download the right ROM?

It just needs to specifically say it's for the N8010 and either your country or all countries. Any N81010 ROM should run but might be in another language. No promises, but if you already have TWRP, PhilZ, or CWM for your bootloader, and an SDcard slot, you should be able to backup your current ROM to the SDcard (or internal memory and copy it to your PC). And if the new ROM doesn't work you should at least be able to flash another ROM or do a restore from the recovery backup. Installing a ROM from recovery doesn't touch the recovery. Tell it to backup everything except the cache.