You're asking a lot fo concrete questions to which there're no universal answers. I'm afraid your question will be closed because of lack of focus.
I'll try to give you some pointers.
What should I first focus on as a beginner with no knowledge in automated testing? Should I first learn C#? Or start directly learn Selenium (or other testing tools?)
Focus on learning where automation can bring value and what information you can gather using it (ask around in your company). There's nothing worse than people who come to this area and start automating everything with no clear goal in mind.
Learn what the layers of the application are and what could you test and check on each one.
Since you mentioned UI, it seems to me that your focus will be on UI only. Learn to limit yourself on this level since checks tend to run long and are closely tight to UI changes, which more often than not means they also break often.
How much experience do I need in C#, to fully use Selenium? Is it enough when I know the basics in C#? Or do I need advanced/expert knowledge in C# for selenium?
You are a Tester, go and test yourself. Give yourself a task to automate something using these technologies. How easy was it? If you feel it was hard, you should probably study more.
Today, I had my first talk with a tester from a other team and he mentioned “Tosca”. I googled the difference between Tosca and Selenium. And both are being used very differently. Maybe someone here used both and could give me his opinion on both testing tools? Are both covering the same test cases?
C#, Tosca, Selenium, ... you mention a lot of technologies but no reasons why these were suggested. Focus on why. Choosing appropriate tools in your context can save you a lot of time later on. Why don't you ask that Tester to tell you why he chose Tosca, or C#, or any other tool? Don't be satisfied with answers such as "that's the way this company runs."
Are there any other tools needed for automated testing beside of Selenium or Tosca, which I should look at?
There're probably tens of other tools you'll (have to) learn. But you won't need all of them every single time. The problem here again is your context. You might use tool A now, but you might find tool B more appropriate on a future project.
All in all, I don't think that focusing too much on particular tools is especially beneficial. In my opinion, tools could be learnt fast, but it usually takes some time to develop the right attitude towards automation as well as the underlying technologies systems are built on.