Neural Network written in Kotlin working for simple math problems but not for MNIST classification
I managed to solve the problem on my own. Turns out that the problem was indeed in the hyper-parameters, as I suspected.
I was using the same values as Michael Nielsen so it seemed strange to me that they could be wrong - by a mathematical point of view, my network is exactly the same as his one! - anyway, lowering the $\eta$ and raising the $\lambda$ (in practice, lowering the weights/biases changes on a single batch) lets the network to better understand which direction it should take to minimize the cost function.
I can now get accuracies above 85%, and I'm sure that with a bit of fine-tuning I can reach at least 95%.
I also solved the cost plot problem:

I can't understand why the cost is increasing instead of decreasing [...]

The problem was that instead of doing something like
$C= -{1 \over n} ∑_{xj} [y_j ln(a^L_j) + (1−y_j) ln(1−a^L_j)] + {λ \over 2n} ∑_w w^2$
I was doing
$C= -{1 \over n} ∑_{xj} [y_j ln(a^L_j) + (1−y_j) ln(1−a^L_j) + {λ \over 2n} ∑_w w^2]$
which doesn't make sense, since the last term equals to
$∑_{xj} {λ \over 2n} ∑_w w^2 = n {λ \over 2n} ∑_w w^2 = {λ \over 2} ∑_w w^2$
and so we get a wrong regularization factor for the weights.