**There is one natural candidate that leaps to mind, namely the construal of $2^G$ as a relation algebra for each group $G$ $\ldots$**

This construction will not answer your question, since each relation algebra of the form $2^G$ is representable. To see this, for each $A\subseteq G$ define a binary relation $\rho_A$ on $G$ by
$
\rho_A :=\{(x,y)\in G^2\;|\; x^{-1}y\in A\}.
$
Now check that<br>
<ol>
<li> $\rho_A\cup \rho_B = \rho_{A\cup B}$
</li>
<li> $\rho_A\cap \rho_B = \rho_{A\cap B}$
</li>
<li> $\rho_A\circ \rho_B = \rho_{A\cdot B}$
</li>
<li> $\rho_{\{e\}} = \Delta$ (the equality relation)
</li>
<li> $\emptyset = \rho_{\emptyset}$
</li> 
<li> $G\times G=\rho_G$
</li>
<li> $(\rho_A)^{\cup} = \rho_{A^{\cup}}$
</li>
<li> $(G\times G)\setminus\rho_A = \rho_{G\setminus A}$.
</li>
</ol>
<br>

These show that $A\mapsto \rho_A$ is a representation of $2^G$. Thus the $2^G$-construction is ``insufficiently surjective''.