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][1], 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][2] 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.

  [1]: https://en.wikipedia.org/wiki/Semidefinite_programming
  [2]: https://mathoverflow.net/questions/142418/point-in-polytope