Gradient Descent - how many values are calculated in loss function?
Gradient descent is based on sources: your data and your loss function.

In supervised learning, at each training step the predictions of the Network are compared with the atcual, true results. The value of a loss function is calcualated, which is telling your model "how wrong it is". At this point, the weights of the Network must be updated accordingly.

In order to do that, a formula based on the chain rule of derivatives calculates retrospectively the contribution of each weight to the final loss value. The value of each weight is then changed, based on their impact on the loss function (mathematically, it's a first partial derivative for each weight). This process is called backpropagation, since it logically starts from the bottom of the Network and is computed backwards up to the input layer.

This process has to be done for each of the Network's learnable weights. The higher the number of parameters, the higher the number of partial derivatives that are computed at each training iteration for the weight update. When all the weights are updated, the position of the Gradient will (hopefully) be a small step closer to the global minimum of the loss function.

Coming to your doubts: grid search on the loss function values is something you can do only in theory, not in practice. It could take an impossible amount of time to do that, even for the most powerful computers. At the moment, the Gradient descent algorithm is the main tool to train Neural Networks. As far as I know, other methods such as Monte Carlo and Genetic algorithms are feasible but not practical, therefore not state-of-the-art.

I suggest you two great posts to understand how Gradient descent and backprop work: this one by Andrej Karpathy and this one by Colah.