The idea behind this paper (and other previous work on "NISQ"-y quantum lattice algorithms) is to translate a hard lattice problem into a binary optimization problem. To show how this works for SVP, let $B$ be a matrix of the basis vectors of an $n$-dimensional lattice $L$. Suppose we want to find the shortest vector $v$. Being shortest is equivalent to being the $v\in L$ which minimizes $v^Tv$. We can further decompose $v=Bx$ for some integer $x$, so we want to find the $x\in \mathbb{Z}^n$ which minimizes $x^TB^TBx$. Even more, we can decompose each component of $x=(x_1,\dots, x_n)$ into binary, as $x_i = x_{i0}+x_{i1}2^1 + x_{i2}2^2 + \dots + x_{im}2^m$ for some $m$, where each $x_{ij}\in \{0,1\}$. Thus, we can rewrite
$$ v^Tv = x^TB^TBx = \sum_{ijk\ell st} x_{ij}2^jB_{si}B_{tk}x_{k\ell}s^\ell = \sum_{ij k\ell} x_{ij}x_{k\ell} C_{ijk\ell}$$
where $C_{ijk\ell}:= \sum_{st} 2^{j+\ell}B_{si}B_{tK}$.
Minimizing $v^Tv$ for $v\in\ell$ is equivalent to minimizing the expression above over all possible binary choices of $\{x_{ij}\}$.
Actually, binary optimization problems are also extremely hard, so this isn't really helpful classically (we've basically thrown away all the geometric lattice structure!). But the helpful fact here is that evaluating this cost function is actually fairly straightforward on a quantum computer.
Once you can evaluate a cost function on a quantum computer, you can try any number of quantum optimization techniques (such asQAOA as in the linked paper, or a variational quantum eigensolver). The details of these aren't important; the relevant fact is that in terms of queries (so, roughly equivalent to runtime), they can't outperform Grover's algorithm. Looking at the above, we have $nm$ binary variables, so the search space is $2^{nm}$ and that means a runtime of $O(2^{nm/2})$. Here they analyze carefully and bound $m= O(\log n)$ (meaning the coefficients don't need to be larger than $O(n)$ for the shortest vector, if the basis is preprocessed). Thus, the runtime is at best $2^{O(n\log n)}$: asymptotically the same as quantum enumeration, worse than quantum sieving (though without the memory requirements).
So if variational/approximate algorithms don't offer an asymptotic improvement on previous algorithms, why do we care? Because these algorithms require only short quantum computations before a classical measurement. Thus, the fault-tolerance overhead can be much lower and hence the qubit requirements of the algorithm are also much lower. Thus, it might be easier to build a huge array of quantum computers that could run a NISQ-y quantum algorithm, rather than the fully fault-tolerant quantum enumeration or lattice sieving.
More precisely, you say "just 25.482, QBits to crack Kyber1024. That is less than for RSA encryption.", which isn't quite right. RSA encryption takes only a few thousand logical qubits, which are high-fidelity qubits with error correction overhead. The best estimates today say that this will need several million physical qubits (the actual components of the quantum computer). In contrast, we might be able to run these NISQ lattice solvers directly on the physical qubits, or with less error correction so that they use fewer than a million physical qubits.
But overall I'm quite skeptical. We have no runtime guarantees on these algorithms, noise can be a big problem, and we just have to hope that the classical optimizer can do a good enough job to find the right solution. It's interesting and worthwhile for quantum cryptanalysts to consider, but I don't think it has any impact on lattice security estimates.
