Can Reinforcement Learning solve problems, where certain elements in the environement are randomly located?
Yes you can use RL for this. The trick is to include the location of the cheese as part of the state description. So as well as up to 400 states for the mouse location, you have (very roughly) $400^{10}$ possible cheese locations, meaning you have $400^{11}$ states in total. 

So you are going to want some function approximation if you want to use RL - you would probably train using a convolutional neural network, with an "image" of the board including mouse and cheese positions, plus DQN to select actions. 

Viewed like this, a game where the mouse tries to get the cheese in minimal time seems on the surface a lot simpler than many titles in the Atari game environments, which DQN has been shown to solve well for many games.

I would probably use two image channels - one for mouse location and one for cheese location. A third channel perhaps for walls/obstacles if there are any.


  Or is the only way to solve this problem to use algorithms like the A*-algorithm?


A* plus some kind of sequence optimisation like a travelling salesman problem (TSP) solver would probably be optimal if you have been presented the problem and asked to solve it any way you want. With only 11 locations to resolve - mouse start plus 10 cheese locations - then you can brute force the movement combinations in a few seconds on a modern CPU, so that part may not be particularly exciting (whilst TSP solvers can get more involved and interesting).

The interesting thing about RL is how it will solve the problem. RL is a learning algorithm - the purpose of implementing it is to see what it takes for the machine to gain knowledge towards a solution. Whilst A* and combinatorial optimisers are where you have knowledge of how to solve the problem and do so as optimally as possible based on a higher level analysis. The chances are high that an A*/optimiser solution would be more robust, quicker to code, and quicker to run than a RL solution.

There is nothing inherently wrong with either approach, if all you want to do is solve the problem at hand. It depends on your goals for why you are bothering with the problem in the first place.

You could even combine A* and RL if you really wanted to. A* to find the paths, then RL to decide best sequence using the paths as part of the input to the CNN. The A* analysis of routes would likely help the RL stage a lot - add them as one or more additional channels.