Smallest $S\subset \mathbb C$ on which no degree $k$ polynomial always vanishes?

Three does not suffice for $n=k=2.$ Consider $x^2+xy+y^2-1$ with the set $\{-1,0,1\}.$

This is probably just another way to present Fedor Petrov's solution: Expand $$\frac{(1-t \alpha_1) (1-t \alpha_2) \cdots (1-t \alpha_{n+k-1})}{(1-t \beta_1)(1 - t \beta_2) \cdots (1-t \beta_n)}$$ as a formal power series in $t$. The coefficient of $t^k$ is a degree $k$ polynomial in the $\beta$'s, which vanishes whenever $\{ \beta_1, \beta_2, \ldots, \beta_n \}$ is a $n$-element subset of the $\alpha$'s.

No. Moreover, for any set $A\subset \mathbb{C}$, $|A|=n+k-1$, you may find a not identically zero polynomial $p_A$ of degree at most $k$ such that $p_A(x_1,\ldots,x_n)=0$ for all distinct $x_i\in A$. For $n=1$ this is already mentioned in OP, so further I suppose that $n>1$.

For $k-1$ variables $t_1,\ldots,t_{k-1}$ denote $p_i=\sum_{j=1}^{k-1} t_j^i$. We may express $p_k$ as a polynomial in $p_1,\ldots,p_{k-1}$. This gives us a polynomial $h$ such that $h(p_k,p_{k-1},\ldots,p_1)\equiv 0$, and $h(z_k,\ldots,z_1)$ is weighted homogeneous with weighted degree $k$: for any monomial $\prod z_i^{c_i}$ in $h$ we have $\sum ic_i=k$. Next, consider $k$-th variable $t_k$ and the polynomial $$F(t_1,\ldots,t_k):=h\left(\sum_{j=1}^{k} t_j^k,\sum_{j=1}^{k} t_j^{k-1},\ldots,\sum_{j=1}^{k} t_j\right).$$ $F$ is symmetric, not identically zero (since $h$ is not identically zero and the guys $\sum_{j=1}^{k} t_j^i$ which we substitute to $h$ may take any complex values), is homogeneous of degree $k$. Also $F$ takes zero value when one of $t_i$'s is zero. Therefore $F$ is divisible by $t_1\ldots t_k$, and since $\deg F=k$ we get $F=c\,t_1\ldots t_k$ for certain non-zero constant $c$.

Now denote $\alpha_i=\sum_{a\in A} a^i$ and take the polynomial $$ p_A(x_1,\ldots,x_n)=h\left(\alpha_k-\sum x_i^k,\alpha_{k-1}-\sum x_i^{k-1},\ldots,\alpha_1-\sum x_i\right). $$ From the above properties of $h$ we get $\deg p_A\leqslant k$ and $p_A(x_1,\ldots,x_n)=0$ whenever $x_1,\ldots,x_n$ are distinct elements of $A$. It remains to show that $p_A$ is not identically zero. For this aim we choose $k$ non-zero elements $a_1,\ldots,a_k\in A$, denote other elements of $A$ by $a_{k+1},\ldots,a_{k+n-1}$ and substitute $x_i=a_{k+i}$ for $i=1,\ldots,n$ and $x_n=0$ to $p_A$. This value of $p_A$ is nothing but $F(a_1,\ldots,a_k)\ne 0$.