I will use the standard notation $e_k$ for the $k$-th elementary symmetric polynomial of $n$ variables, and just $e$ instead of $e_1$ for better readability.

For $k\le n$, denote the set of the "base polynomials" of degrees $\leqslant k$ that are writable in terms of $x,y,e_1,e_2,\cdots,e_{k-1}$, possibly including coordinate-wise products as in the OP, by $P_{k-1}$.

For a partition $k=\ell+m$, define, in somewhat sloppy notation, the symmetric polynomial
$$E_{(\ell,m)}:=\sum (x_1\cdots x_\ell y_{\ell+1}\cdots y_k +y_1\cdots y_\ell x_{\ell+1}\cdots x_k ).$$
So the sum is over all pairs of disjoint $\ell$- and $m$-tuples of indices. (If $\ell=m$, each monomial occurs twice, but we will count it only once.)

For instance, the following sum has $8$ monomials, and it can be checked that we can decompose it into polynomials of $ P_{3}$ as follows:

$$E_{(3,1)}=\sum (x_1x_2x_3y_4+y_1y_2y_3x_4)=\\ e_3(x)e(y)+e_3(y)e(x)-[e_2(x)+e_2(y)]e(xy) \\ +e(x)e(xxy)+e(y)e(yyx)-e(xxxy)-e(yyyx).$$ (BTW this splits of course into two non-symmetric identities, one which contains all terms featuring three instances of $x$ and one of $y$, and the other one switching $x\leftrightarrow y$.)

Now, taking $k=4$, it is easy to see that we have $$e_k(x+y)-e_k(x)-e_k(y)=E_{(3,1)}+E_{(2,2)}$$ but it seems to me that
$$E_{(2,2)}=\sum x_1x_2y_3y_4$$ can **not** be decomposed into polynomials of $ P_{3}$ . *Or am I wrong?*

pairingof the two alphabets $X=\{x_i\}_{i\in I};\ Y=\{y_i\}_{i\in I}$ is not conventional (although you may need it), setting $X+Y=\{x_i+y_i\}_{i\in I}$ destroys the symmetry of the expression $S_k(X+Y)-S_k(X)-S_k(Y)$. Are you aware of this ? What is used as definition of the sum is $$X+Y=\{x_i+y_j\}_{i,j\in I}$$ In this case Alexander Woo's formula is right. $\endgroup$ – Duchamp Gérard H. E. Apr 16 '15 at 4:45