So far, University was mostly lectures, seminars and exams.
The scope of problems to solve was usually very narrow and the necessary knowledge was taught in the lecture or seminar.
Solving a given problem in a seminar or exam was done by picking the right tool from the toolbox that one gathered over the year. There was often one specific workflow/formula/strategy/etc. to solve a particular problem. Sure, some of them allowed for some tweaks to get the job done faster, but for the most part the goal was the solution that the problem was asking for. There was never a need nor time to explain the reason to choose a certain method.
Now doing research for thesis, things appear to be different. There's one bigger problem to be solved. There's also some paper to be filled with text about the solution I came up with. I could just solve the problem and document what I've done. However, I got the feedback on previous smaller "publications" that such a document should not just be a manual to understand the solution, but to show the research that was done.
Research seems to have the inherent property to be open ended and unpredictable. Whenever I make a decision, I have the nagging doubt that I should explore more/all the choices and compare them, so that nobody asks me at the end why I haven't tried that other option, too. Previously, the reason to solve a problem in a certain way was because I was taught to solve it that way and arriving at the solution was good enough.
For research, that seems to be different. As the existence of a solution is never guaranteed, it's not so important to actually arrive at a solution, but how to get there. An attempt at solving the problem (or any sub-problem) or really doing anything at all might fail or not, which begs the question why if failed or not. How do I make an educated decision about when to dig deeper and when not to? How do I choose the right level to explore variations? (for example, when to just modify some parameters of a program, use a different mode of the program, choose a different program altogether, use a different computer[, set everything on fire, throw it out of the window and start from scratch])
It's not possible to try everything and making the right decision on what to try and what not to try seems to be a matter of (a lot of) experience, which I do not have at all. How do I make those decisions? Should I just follow my gut feeling and try things, because even if they fail: that's a result? But what if it turns out that even trying those things wasn't a reasonable thing to do in the first place? That would be bad then, wouldn't it? How to get out of this dilemma?
Firstly, don't worry. This anxiety that you describe is extremely common and completely normal. You're right that it stems from the transition from very tightly-constrained styles of work to something that is much more open-ended. You are half-way there - you have recognised that you have many different possible paths to follow. But I get the impression that you are still thinking in terms of pass and fail. You talk about finding the "right decision", and that a given approach "might fail or not", but research is not so black-and-white.
Of the many different paths that you are considering, it's not that some of them contain death-traps where you will be forever doomed, whereas some are shining paths to glory. It is likely that you can make a success of any of them (just so long as you don't stay rooted to one spot for too long...). Even a "failure" to find a solution is useful. In the words of Thomas Edison:
"I have not failed. I've just found 10,000 ways that won't work."
You might find inspiration for something else, or you might just be able to rule out one method - that is still progress.
You also talk about whether to pursue a single issue in depth, or take a radical change of direction. Both those approaches are valid, and it's up to you which style you prefer. Eventually, with experience, you will start to get a bit of a nose for what sorts of approach work best for you, and maybe be able to head in a slightly straighter line through your research. But even professors are not perfect in that regard. Until then, as @user37208 suggests in the comments, your advisor should be a great source of advice here and can help you to break down the problem into more manageable chunks, and give you a bit of direction when you feel you are wandering around without success.
You may be thinking "that's all very well, but at the end of the day, my thesis will pass or fail." While that's true, this will depend far more on how well you can explain what you have done, and whether you can demonstrate that you have made reasonable efforts to tackle one or more problems, than on whether you have actually found "an answer" or not.