Let's just remind ourselves what k point sampling is. It is used to approximate the integral of a function over the Brillouin zone by replacing the integral with a sum over a finite number of points:
$$
\int_{BZ} F({\bf k})d{\bf k} \approx \sum_j w_j F({\bf k_j})
$$
Now this is an approximation, and for any relatively sane function the error in this approximation will decrease with the number of sampling points, and eventually converge to the correct value. But note there is absolutely nothing which says what the sign of the error is. It could be positive. It could be negative. And whether it is positive or negative could vary with the number of sampling points. Thus it is far from uncommon to see the total Energy increase when you initially increase the number of k points, and then show damped oscillations about the converged value, which is what you seem to be observing.
Compare this with how the total energy changes with respect to variations in the wavefunction. Here the variational principle applies, so any approximate wavefunction will result in a total energy higher than the ground state energy, unless the wavefunction is exactly the ground state wavefunction. Thus we can solve for the ground state wavefunction (and energy) by a minimization procedure. However for k point sampling this principle does not apply, and thus we can see errors of either sign - k point sampling is not variational, but enough k points will converge to the true value (or more strictly to within a desired error from the true value)
