[Expanding the comment into an answer.]
First, just a clarification about counting bound variables in a combinator (= closed term) $t$. I interpret the question as asking about
$$
\text{the total number of distinct bound variable names in }t
$$
so that for example the term $t = (\lambda x.x(\lambda y.y))(\lambda x.\lambda y.yx)$ counts as having two bound variables, despite having four binders (i.e., lambda abstractions). This way of counting was initially a bit strange to me since it is not invariant under $\alpha$-conversion: for example, $t$ is $\alpha$-equivalent to $t' = (\lambda x.x(\lambda y.y))(\lambda a.\lambda b.ba)$, but $t'$ has four distinct bound variable names. However, this is not really a problem, because the minimum number of distinct bound variable names needed to write a closed term $t$ is equal to
$$
\text{the maximum number of free variables in a subterm of }t
$$
and the latter notion is invariant under $\alpha$-conversion.
So, let $\mathcal{C}$ be the collection of all combinators which can be written using at most two distinct bound variables, or equivalently the collection of all combinators whose subterms have at most two free variables.
Theorem (Statman): $\mathcal{C}$ is not combinatorially complete.
It seems that the original proof of this is contained in a tech report by Rick Statman:
- Combinators Hereditarily of Order Two. Carnegie Mellon Math Department Technical Report 88-33, August 1988. (doi)
Statman defines an essentially isomorphic collection of combinators which he calls "HOT", for "hereditarily of order two". The tech report actually shows that the word problem (i.e., $\beta$-equality) for HOT is still undecidable, despite the fact that it is not combinatorially complete. Statman later wrote a short self-contained paper with the proof that HOT is not combinatorially complete in:
- Two variables are not enough. Proceedings of the 9th Italian conference on Theoretical Computer Science, pp. 406-409, 2005. (acm)
In any case, as glossed in the abstract of the original tech report, the idea of the proof is to show that HOT is a "hierarchy by definitional level". That is, he defines a notion of rank for a HOT combinator, and a family of combinators $Hn$, such that each $Hn$ has rank $n+1$ and is not $\beta$-equivalent to any combination of HOT combinators of rank $n$. This implies that HOT is not combinatorially complete, because if the $S = \lambda x.\lambda y.\lambda z.(xz)(yz)$ combinator could be derived from a combination of HOT combinators of rank $n$ for some $n$, then so could any other combinator, in particular the combinator $Hn$ of rank $n+1$.
