I can make a little progress here. One of your key subproblems is: Given a computable group $G$, a finite list of elements $T \subseteq G$ and an element $\alpha \in \mathbb{Q}[G]$, determine whether there exist $\xi_1$, $\xi_2$, …, $\xi_k$ in $\mathbb{R} T$ so that $$\alpha = \sum_{i=1}^k \xi_i \xi^{\ast}_i.$$
This problem can be solved by semidefinite programming, which is a field of numerical analysis with well-developed toolkits. In particular, I will solve the above problem for all $k$ at once.
Write the elements of $T$ as $g_1$, $g_2$, ..., $g_t$ and write $$\xi_i = (g_1 \ g_2 \ g_3 \ \cdots \ g_t)^T \cdot a_i$$ where $a_i \in \mathbb{R}^t$. Then the above equation is $$\alpha = (g_1 \ g_2 \ g_3 \ \cdots \ g_t)^T \left( \sum_{i=1}^k a_i a_i^T \right) (g_1^{-1} \ g_2^{-1} \ \cdots \ g_t^{-1} ).$$
Recall that a $t \times t$ real matrix $X$ can be written as $\sum a_i a_i^T$ if and only if $X$ is positive semidefinite. So your question is does there exist a matrix $X$ such that
(1) $X$ is positive semidefinite and
(2) $\alpha = (g_1 \ g_2 \ g_3 \ \cdots \ g_t)^T X(g_1^{-1} \ g_2^{-1} \ \cdots \ g_t^{-1} )$
Note that condition (2) is an affine linear condition on $X$. Solving linear equations with the constraint that variables be positive semidefinite matrices is what SD programming is all about.
Working a little bit harder, you should be able to copy Peter Shor's trick here and maximize $r$ subject to the SD program $$\Delta^2 = r \Delta + (g_1 \ g_2 \ g_3 \ \cdots \ g_t)^T X(g_1^{-1} \ g_2^{-1} \ \cdots \ g_t^{-1} ),\ X \ \textrm{positive semi definite};$$ so you get a spectral gap if the optimal $r$ is positive.
I expect the hard part will be choosing the set $T$ to use; I have no ideas about this.
