I might be misreading something, but how can you pick 2^(k) elements from S, which seems to have only k elements?

I'm not sure I follow your proof (I can look at it more closely later), but note that every positive element of S is just a string of 2s in base 3.