Solving a system of sums-of-powers polynomials
I think your question is closely related to the set reconciliation problem, which is solved in this paper: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.5338

The problem of set reconciliation is to given two sets $A, B \subseteq [n]$ find $A \backslash B$ and $B \backslash A$ with as less communication as possible. If $B = [n]$, then you just need to find $\bar A$. Authors provide an algorithm with $O(k \log n)$ communication complexity.

Basic idea of the algorithm is to find small prime number $p$ greater than $4n$ and compute next two polynomials $\chi_A(x) = \prod_{a\in A} (x - a)$ and $\chi_B(x) = \prod_{b \in B} (x - b)$ in $\mathbb{F}_p$ on $2 \cdot k$ different points.

It can be easily shown that $$\frac{\chi_A}{\chi_B} = \frac{\chi_{A \cap B} \cdot \chi_{A \backslash B}}{\chi_{A \cap B} \cdot \chi_{B \backslash A}} = \frac{ \chi_{A \backslash B}}{ \chi_{B \backslash A}}.$$

If you compute these polynomials in non-zero points (for example, greater than $n$), then you obtain $2 \cdot k$ equations of the form
$$
\chi_{A \backslash B}(x_i) \cdot b_i = \chi_{B \backslash A} \cdot a_i,
$$
where $a_i$ and $b_i$ are corresponding values of $\chi_A$ and $\chi_B$ at $x_i$.

System of $2k$ equations with $2k$ variables over field $\mathbb{F}_p$ can be easily solved. The last thing is to factorize polynomials. The authors provide easy algorithm for this case.

Turning back to your first question $\chi_{\bar S}(x)$ can be expressed with your $s_i$'s for $i$ from $0$ to $k$.