Dear Giovanni, I did not understand what statement should I confirm by a reference. I claimed that for an explicitly given metric one can algorithmically understand the dimension space of Killing tensors of a given degree. This is a folklore but I do not know a good reference. Now, once we have the dimensions of the spaces of Killing tensors of degree less or equal to $k$, we know whether there exists a Killing tensor of degree k by counting the dimensions. Does it help.

Dear Giovanni, The Killing equations is a an overdetermined linear system of PDE of finite type and in theory there exists an algorithm that decides whether a given metric admits a Killing tensor of a given degree and determine the dimension of the space of Killing tensors. Then, this algorithm also answers whether a metric admits a non-reducible Killing tensors of some degree. To be precise, the algorithm is local and gives the answer in a neighborhood of almost every point. The algorithm is computationally very hard even in simple situations.

Thank you, Robert. It may happen that I used wrong terminology in my question: instead of "normal forms" I should say "local description". I am indeed more interested in the answer of the form: "in a certain coordinate system, the pair $(g, L)$ are given by ...". So, from this point of view, the case $L=0$ is trivial, since in a certain coordinate system the metric is given by arbitrarily $g_{ij}(x)$ and $L$ is identically zero. P.S. It is indeed true that the most complicated cases are when $L$ has many Jordan blocks with the same eigenvalue and of approximately same dimensions.

I just checked the reference Matias Dahl has given and I did not know before: it gives a precise answer to your question (though it is possible to obtain this answer "by hand"). The rough answer is as follows: in a certain basis the matrix of $L$ has the standard Jordan normal form. The matrix of $g$ is also block-diagonal with the same dimensions of the blocks as the matrix of $L$; each block is (up to the sign) the anti-diagonal 1-matrix (i.e., the elements $a_{i , k-i+1}$ are 1 and other are 0).

Thank you, Matias; I did not know this reference and therefore had to obtain the same local description by hands.