Colored cliques complexity
Your problem is in NP.  (A certificate for a "yes" answer is to list one of the $k$-cliques that each edge is contained in.)  Therefore, it's not likely to be PSPACE-complete: if it were PSPACE-complete, that would imply NP = PSPACE, which would be surprising.

Your problem is NP-complete.  It is at least as hard as the $k$-clique problem. Suppose we have a graph and we want to know whether it contains a $k$-clique.  Then we can color all edges green, let $\alpha$ be the empty list, and let $\epsilon$ be the list containing only the color green.  Now the graph has a $k$-clique if and only if the answer to your problem is yes.  But testing for a $k$-clique is NP-complete, so it follows that your problem is NP-complete too.