This problem ended up being more disgusting than I anticipated. Anyway, here's my solution:

Same idea was used in 2009 China TST. https://artofproblemsolving.com/community/c6h269070p1458327

You forgot to check if $n-1$ is minimum, @above.

I have a doubt. It is true that $$P(n+k) \equiv P(k) \mod n$$So we can just fix the values the polynomial takes at $0,1,2,\ldots ,n-1$ and we know that a unique polynomial exists satisfying these values due to Lagrange interpolation. We can do this for any $S$. So why should there sometimes be no smallest $d$? @below thanks

Your polynomial $P$ will have rational coefficients instead of integer coefficients.

Holy crap that was long The answer is for $n = 4$ and $n$ prime, we have $d = n-1$, while for all other $n$ $d$ can not exist. Define a polynomial $P$ as covering a subset $T$ if $T$ is the image of $P$ in $\mod n$. First, observe that if a $d$ does not exist for some $n$, then it does not exist for any multiple of $n$ either. This is because, let's say $T$ was the subset where no polynomial existed; if $d$ exists for some multiple $kn$, then the set $T$ is also covered by a polynomial, but taking such a polynomial in $\mod n$ would result in $T$ getting covered, a contradiction. Now, we will prove that 1. Numbers in the form $n = pq$ for distinct primes $pq$ do not contain $d$ 2. Numbers in the form $n = p^{2}$ for odd primes $p$ do not contain $d$. 3. Numbers in the form $n = 8$ do not contain $d$ This is enough to show that the only numbers which can contain $d$ are primes and $n = 4$ (because, by the multiple of $n$ result, $n$ which are powers of primes (besides $4$) or contain multiple prime divisors will fail). Case 1: We will show $n = pq$ for distinct primes $p,q$ fails. Consider the subset $(0,1)$; I claim no polynomial covers this. Assume some polynomial $Q\in \mathbb{F}_{n}$ covered this; then if $Q(k) = 0$ for some $k$, let $P(x) = Q(x+k)$, so $P(0) = 0$. Then, $P$ does not contain a constant term. Consider $P(ap)$ for some integer $a$. Since there is no constant term, it means $p | P(ap)$, so $P(ap) = 0$. Similarly, $P(bq) = 0$ for all integers $a, b$. Then, if some $m = ap + bq$ where $P(m) = 1$, we have \[ap | ap + bq - bq | P(ab + bq) - P(bq) = P(m) - 0 = 1\]Contradiction. Case 2: We will show that $n = p^{2}$ for odd prime $p$ fails. Consider the subset \[T = \{a | a\not\equiv 0\mod p\}\cup\{0\}\cup\{p\}\]Again, assume some polynomial $P$ covers this. Using the same trick as last time we can assume $P$ has no constant term (also implies $P(0) = 0$). Then, for every number in the form $ap$, where $p\not|a$, clearly $p | ap | P(ap) - P(0) = P(ap)$. If $P(ap) = p$, then consider the coefficient $r$ of the $x$ term in $P$. We can rewrite $P(x) = Q(x) + rx$ where $Q$ does not contain a constant nor an $x$ term. Then, this means $p^{2} | Q(ap)$ (since the exponent of each $x$ term in $Q$ is at least $2$), so $p\not| r$ or else $P(ap) = 0$. But then, consider $P(p), P(2p)$. They're both equal to $p$, so \[rp = Q(p) + rp = P(p) = P(2p) = Q(2p) + 2rp = 2rp\]But since $p\not | r$, this is a contradiction. Thus, for all $ap$, we have $P(ap) = 0$. Now, there are $p(p-1)$ residues of $p^{2}$ that are not divisible by $p$, but we have $p(p-1) + 1$ more residues that $P$ can take on (besides $0$), a contradiction by pigeonhole. Case 3: We will prove $n = 8$ does not contain a $d$ value. Consider the set $T = (0,1,2,3,5,7)$, and we use the trick of $P(0) = 0$ with $P$ not having a constant term. Then, let \[P(x) = Q(x) + ax^{2} + bx, x^{3} | Q(x)\]Consider $P(4)$. It has to be even, and divisible by $4$, which means $P(4) = 0$. Since $8 | Q(4) + a\cdot 4^{2}$, we must have $8 | 4b$, so $b$ is even. Next, consider $P(2), P(6)$. Rewrite $b = 2b'$. We have \[4 | Q(2) + 4a + 4b' = P(2)\Rightarrow P(2) = 0\]Similarly, $P(6) = 0$. Now, there are $4$ remaining residues ($1,3,5,7$), but $5$ values for them to attain ($1,2,3,5,7$), a contradiction by pigeonhole principle. Thus, $n = 8$ does not contain a $d$ value. Now, we only need to focus our attention on $n = 4$ and $n = p$ for some odd prime $p$. I claim for primes $p$, $d = p-1$ is achievable and minimal. To show that is achievable, let the elements of a subset be $\{0, a_{1}, a_{2}, \ldots a_{k}\}$ where $a_{i} < a_{i+1}$. Then, consider the polynomial \[P(x) = \sum_{i=1}^{k}a_{i}(1 - (x-i)^{p-1})\]By Fermat's little theorem, $1 - y^{p-1}$ is only $1$ when $y = 0$. Thus, every $a_{i}$ is achieved, and $0$ is achieved when $x = 0$. Furthermore, no other value can be achieved. Then, for an arbitrary subset of $S$, we can just add a constant $c$ to this polynomial to shift all the values to get any arbitrary subset. Now we will prove that $p-1$ is minimal. First, let's prove the following two lemma: Lemma 1: For any integer $k < p-1$, we have \[\sum_{i=0}^{p-1} i^{k}\equiv 0\mod p\] Proof: Let $g$ be a primitive root $\mod p$, so since $P(i) = g^{i}$ is a permutation of the residues, we have \[\sum_{i=0}^{p-1}i^{k} \equiv \sum_{i=0}^{p-2}g^{ik} \equiv \frac{g^{(p-1)k} - 1}{g^{k} - 1}\equiv 0\mod p\] Lemma 2: For any polynomial $P$ with degree less than $p-1$, we have \[\sum_{i=0}^{p-1} P(i)\equiv0\mod p\] Proof: Let \[P(x) = a_{k}x^{k} + a_{k-1}x^{k-1} + \ldots a_{1}x + a_{0}\]Then, \[\sum_{i = 0}^{p-1}P(i) \equiv \sum_{i=0}^{p-1}\sum_{j=0}^{k} a_{j}i^{j} \equiv \sum_{j=0}^{k}a_{j}\sum_{i=0}^{p-1}i^{j} \equiv \sum_{j=0}^{k}a_{j}\cdot 0 \equiv 0\mod p\] Now, consider the subset $T = \{0, 1\}$. If $p > k > 0$ residues gets mapped to $1$, and the other $p-k$ gets mapped to $0$, then \[P(0) + P(1) + \ldots + P(p-1) \equiv k \not\equiv 0\mod p\]Contradiction. Thus, $p-1$ is minimal for primes. We are almost done. Now we just need to check the case for $n = 4$. To show that $d = 3$ is achievable, we have the following polynomials: \[0,1,2,3, x^{2}, x^{2} + 1, x^{2} + 2, x^{2} + 3, 2x^{2}, 2x^{2} + 1, x^{3}, x^{3} + 1, x^{3} + 2, x^{3} + 3, x\]Now we show it is minimal. I claim the subset $\{0, 1, 3\}$ is not coverable by any polynomial with degree at most $2$. We can use the same trick as before; assume $P(0) = 0$, so $P$ does not have a constant term. Let $P(x) = ax^{2} + bx$, where $0 \leq a,b < 4$. If $b$ is even, then $3\cdot b\equiv 1\cdot b\mod 4$, which implies $P(3)\equiv P(1)\mod 4$. This also implies $P(2)\equiv 0\equiv P(0)\mod 4$, a contradiction since we need three values. Thus, $b$ is odd. However, this means $P(2)\equiv2\mod 4$, a contradiction since $2$ is not in the subset. Thus, $3$ must be minimal. We conclude that for $n$ prime and $n = 4$, the answer is $n - 1$, while any other $n$ results in $d$ not existing.

The answer is $d=n-1$ for $n$ is prime or $n=4$, and no $d$ exists for all other $n$. Case 1: $n$ is a prime, call $p$. The answer is $p-1$. It is sufficient by Lagrange Interpolation. I need to show it is necessary. Consider $S=\{0,1\}$. By Lagrange interpolation on $0,\cdots,p-1,$ $$f(x)=\sum\limits_{i=0}^{p-1} \frac{f(i)\prod\limits_{j\ne i} (x-j)}{\prod\limits_{j\ne i}(i-j)}$$ Note \[\prod\limits_{j\ne i}(i-j) \equiv \prod_{i=1}^{p-1} i\equiv (p-1)!\equiv -1(\bmod\; p)\] Comparing the $x^{p-1}$ coefficient, we can see $[x^{p-1}]f(x)=-\sum\limits_{i=0}^{p-1} f(i)$. However, $\sum\limits_{i=0}^{p-1}f(i)$ can be $0$ only if $f(i)=0$ or $f(i)=1$ for all $i$, false. Case 2: $pq\mid n$. Consider $S=\{p,q\}$. Suppose $f(x)=q,$ then $f(x+q)=f(x+2q)=\cdots=f(x+(p-1)q)=q$. Now, if $f(y)=p, $ there exist $l$ such that $l\equiv y(\bmod\; p), l\equiv x(\bmod\; x)$, so $f(l)\equiv 0(\bmod\; p), f(l)\equiv 0(\bmod\; q), $ so $f(l)=0$, false. Case 3: $n=p^k$ for some $p$ odd, $k\ge 2.$ I will first prove this for $k=2.$ Consider $S=\{0,1,\cdots,p\}$. I claim this set fails. We transform $f$ such that $f(0)\equiv 0(\bmod\; p^2)$. If $f(x)=\sum a_ix^i, f(kp)\equiv a_1kp(\bmod\; p^2)$ since $f(0)\equiv 0(\bmod\; p^2)$. This implies $p^2\mid f(kp)$ for all integers $k$. Then we have $p$ remainders mod $p$, but we have $f(1),\cdots,f(p-1)$. Since $f(x+p)\equiv f(x)(\bmod\; p)$, only $p-1$ of those remainders can be filled, false. Now, the same set works for $p^k$ for the same reason, if I take mod $p^2$. Taking mod $p^k$ for $k>2$ is stronger than taking mod $p^2$. Case 3: $n=4$. The answer is $3$. Increment each element in $S$ by a constant, such that $0\in S$. If $S$ contains 1 element, $f(x)=0$ is ok. If $S=\{0,i\}$ then $f(x)=ix^2$ works. If $S=\{0,1,2,3\}, f(x)=x$ works. If $S$ doesn't contain $2$, then $f(x)=x^3$ works. If $S$ doesn't contain $k$, then $f(x)=x^3+(k-2)$ works. It can be easily verified that there doesn't exist a degree 2 polynomial for this case. Case 4: $n=2^k, k\ge 3$. No such polynomial exists. Again, it suffices to prove this for $n=8$. Note $x^4\equiv x^2(\bmod\; 8)$ so we will assume $\deg f\le 3.$ Let $f(x)=a_3x^3+a_2x^2+a_1x$ I claim $\{0,1,2,4\}$ fails. Transform $f$ such that $f(0)\equiv 0(\bmod\; 8)$, then it follows $f(1),f(3),f(5),f(7)\equiv 1(\bmod\; 8)$ because otherwise there would be no odd numbers. Since $f(2)\equiv f(6)(\bmod\; 4)$ it follows that $f(2)\equiv f(6)\equiv 2(\bmod\; 8)$ as $4\mid f(4)$. Hence $8\mid a_1(6-2)$, so $a_1$ is even. However, plugging $x=4$ yields $4a_1\equiv 4(\bmod\; 8)$, false.

Like this one ! Case 1:For each prime number $p$ , the minimum possible value for $d$ , is $p-1$. First , we'll show that for each non-empty set $S\subseteq \{0, 1, \ldots, p-1\}$ , there exist a polynomial $P(x) \in \mathbb{Z}[X]$ with such a set of residues modulo $p$and with degree at most $p-1$ and for that , we show that for each arbitrary natural number $a_i$ for $0 \le i \le p-1$ we can make such a polynomial that : $$P(i) \equiv a_i \pmod{p}$$So by Lagrange interpolation one can see that : $$P(x)=\sum_{i=0}^{p-1} {P(i)}\frac{\prod_{j \ne i}{(x-j)}}{\prod_{j \ne i}{(i-j)}}$$And since values of $\prod_{j \ne i}{(i-j)}$ are obviously coprime to $p$ for each $i$ , by CRT we can choose such a number $P(i)$ that we have : $$P(i) \equiv a_i \pmod{p} , P(i) \equiv 0 \pmod{\prod_{j \ne i}{(i-j)}}$$Which implies that the coefficients of $P(x)$ are integer. Now we'll show that for each natural $n \le p-2$ , we have $p|\sum_{i=1}^{p-1}i^n$. So if $gcd(n , p-1)=d$ and $g$ is a primitive root modulo $p$ , values of $i^n$ are equivalent to values of $g^{di}$ for $1 \le i \le p-1$. Now since values of $di$ produce $\frac{p-1}{d}$ distinct values modulo $p-1$ , so if $r_1 , r_2 , ... , r_{\frac{p-1}{d}}$ are all distinct residues of $i^n$ values modulo $p$ , they are roots of polynomial $x^{\frac{p-1}{d}}-1$ modulo $p$ , so by Vieta formula and since $d<p-1$ one can see that : $$x^{\frac{p-1}{d}}-1 \equiv (x-r_1)...(x-r_{\frac{p-1}{d}}) \pmod{p} \implies p|\sum{r_i} \implies \sum{i^n} \equiv d \sum{r_i} \equiv 0 \pmod{p} $$Now put $S=\{1 , 2 , ... , p-1\}$ , then if $deg(P)\le p-2$ we have $p|P(0)+P(1)+...+P(p-1)$ and as the result there exist a number $n$ that $p|P(n)$ while $p|1+2+...+p$ which is a contradiction. So we're done. Case 2 : for each odd prime number $q$ and natural number $n \ge 2$ , there doesn't exist such a number $d$ for $q^n$. Suppose a polynomial $P(x)$ with integer coefficients , now for a natural number $t \in \mathbb{N}$ , we know that there exist a $k \in \mathbb{N}$ that for each integer $x$ we have : $$P(x)+kq^{n-1} \equiv P(x+tq^{n-1}) \pmod{q^n}$$Now by checking binomial expansion of $P(x)$ , we can get : $$P(x+tq^{n-1}) \equiv P(x)+tq^{n-1}P'(x) \pmod{q^n} \implies tP'(x) \equiv k \pmod{q} , P'(x+tq^{n-1}) \equiv P'(x) \pmod{q} \implies P(x+tq^{n-1})+kq^{n-1} \equiv P(x+2tq^{n-1}) \pmod{q^n}$$Now we'll show that the set $S=\{0 , 1 , ... , q^{n-1}\}$ can't be the set of residues modulo $q^n$ for a polynomial $P(x)$. Suppose not and note that each residue in $S$ belongs to the value of $P(x)$ for one value of numbers modulo $q^{n-1}$ then there exist natural numbers $i , t \in \mathbb{N}$ such that : $$P(i) \equiv 0 \pmod{q^n} , P(i+tq^{n-1}) \equiv q^{n-1} \pmod{q^n} \implies P(i+2tq^{n-1}) \equiv 2q^{n-1} \pmod{q^n}$$Which while $2q^{n-1}$ isn't a member of the set $S$ , this is a contradiction. Case 3:if for number $n \in \mathbb{N}$ , there exist two distinct prime factors $p ,q$ which divide $n$ , then there doesn't exist such a proper value for $d$. We'll show that the set $S=\{0 ,1\}$ can't be the set of residues modulo $n$ for a polynomial $P(x)$. Suppose that for a natural number $m$ , we have $n|P(m)$ , then since by CRT for each number $j$ , there exist a number $m_{j} \in \mathbb{N}$ that $m_{j} \equiv j \pmod{q}$ and $m_{j} \equiv m \pmod{p}$ , then we have $n|P(m_{j})$ ( because $P(m_{j}) \equiv 1 \pmod{n}$ is a contradiction while $p|P(m_{j})$ ) and while for each natural number $t$ there exist a $j \in \mathbb{N}$ that $t \equiv m_{j} \pmod{q}$ we have $q|P(t)$ which implies $n|P(t)$ , and that is a contradiction. Case 4:for each natural number $n \ge 4$ , there doesn't exist such a proper number $d$ for $2^n$. Put $S=\{0 , 1 , ... , 2^{n-2}\}$ , now since $2(n-2) \ge n$ , again by binomial expansion of a polynomial with integer coefficients $P(x)$ we can get : $$P(x+t2^{n-2}) \equiv P(x)+t2^{n-2}P'(x) \pmod{2^n} \implies P(x+t2^{n-2})-P(x) \equiv P(x+t2^{n-1})-P(x+t2^{n-2}) \pmod{2^n}$$Now just like case $2$ , there exist natural numbers $i , t \in \mathbb{N}$ such that $P(i) \equiv 0 \pmod{2^n}$ and $P(i+t2^{n-2}) \equiv 2^{n-2} \pmod{2^n}$ and as the result , $P(i+t2^{n-1}) \equiv 2^{n-1} \pmod{2^n}$ which is a contradiction while $2^{n-1}$ is not a member of set $S$. Case 5:For number $n=8$ , there doesn't exist such a proper value for $d$. Again for each polynomial with integer coefficients $P(x)$ and $x \in \mathbb{N}$ one can see that : $$P(x+2) \equiv P(x)+2P'(x)+2P"(x) \pmod{8}$$Since all coefficients of polynomial $P"(x)$ are even , one can see that $P(x+4)-P(x+2) \equiv P(x+2)-P(x) \pmod{8}$ and as the result if we put $S=\{0 , 1 , 2\}$ , similar to above case , there will be a natural number $n$ that $P(n) \equiv 4 \pmod{8}$ , which is a contradiction. Case 6:For number $n=4$ , $3$ is the minimum possible value for $d$. if $deg(P) \le 2$ , one can easily see that we have : $$P(2)-P(0) \equiv P(3)-P(1) \pmod{4}$$and if $S=\{0 , 1 , 3\}$ then one side of this equality will be $0$ and another one $2$ , which is a contradiction. And for $d=3$ these $15$ polynomials will produce all possible subsets of $S$ as a residues set modulo $4$ : $$0,1,2,3, x^{2}, x^{2} + 1, x^{2} + 2, x^{2} + 3, 2x^{2}, 2x^{2} + 1, x^{3}, x^{3} + 1, x^{3} + 2, x^{3} + 3, x$$So we're done.

We claim that $d$ only exists when $n=4$ or $n$ is prime and $d=n-1$ in both the cases. Claim: All the subsets of $\{0, 1, \dots, n-1\}$ are $d$-coverable when $n$ is a prime. Proof: Define the sequence $\{P(0), P(1), \dots, P(p-1) \pmod{p}\}$ to be the signature of a polynomial $P$ modulo $p$. We will count the number of distinct signatures possible so consider $$P(x)=a_{p-1}x^{p-1}+a_{p-2}x^{p-2}+\cdots a_1p+a_0$$where the coefficients are in $\mathbb{F}$, notice that we need $deg P \leq \varphi(p)=p-1$ as everything cycles after that. We have $p$ choices for each coefficient thus we have atmost $p^p$ distinct signatures, now if two polynomials had the same signature, by say lagrange interpolation, the polynomials must be the same in $\mathbb{F}_p$, so we have $p^p$ distinct signatures. Now these signatures constitute all possible subsets of $\{0, 1, \cdots, p-1\}$ so we have proved that all subsets can be covered for $d=p-1$. Now for the lower bound, FTSOC $d\leq p-2$ works, suppose we want to construct a polynomial such that the subset $\{0, k\}$, where $gcd(k, p)=1$. By lagrange interpolation, $$P(x)=\sum_{0 \leq i \neq j \leq p-1} \prod_{i \neq j} \frac{x-i}{j-i}$$since we have information at $p$ points. As $deg P\leq p-2$, we want the leading coefficient to be $0$ so, $$[x^{p-1}]P(x)=\frac{P(0)}{0!(p-1)!}+\frac{P(1)}{1!(p-2)!}+\cdots+\frac{P(p-1)}{0!(p-1)!}$$$$[x^{p-1}]P(x)=\sum_{0 \leq i \leq p-1} (-1)^i \binom{p-1}{i}P(i)$$Now since, $$\binom{p-1}{i}=\frac{(p-1)(p-2)\dots(p-i)}{i!} \equiv (-1)^i \pmod{p}$$we have that, $$\sum_{0 \leq i \leq p-1} P(i) \equiv 0 \pmod{p}$$but this means that all of the $P(i)$ have to be either $0$ or $k$ which is a contradiction. $\blacksquare$ Claim: If $n$ is divisible by at least two primes, all the subsets of $\{0, 1, \dots, n-1\}$ are not $d$-coverable. Proof: Now if $n$ is divisible by at least $2$ primes say $p$ and $q$, let $P$ be the polynomial that covers the subset $\{p, q\}$. By the periodicity lemma($x-y \mid P(x)-P(y)$), we can find $a$ and $b$ such that $P(a) \equiv 0 \pmod{p}$ and $P(b) \equiv 0 \pmod{q}$. Now by CRT, we can find $c$ such that $c \equiv a \pmod{p}$, $c \equiv b \pmod{p}$ and $P(c) \equiv 0 \pmod{pq}$ but this means $0$ is coverable too which is a contradiction. $\blacksquare$ Claim: The only prime power $n$ for which all subsets of $\{0, 1, \dots, n-1\}$ is $d$-coverable is $4$. Proof: Suppose $n=p^a$ where $p$ is odd, consider the set $\{0, 1, \dots, p\}$. Suppose $P(n_1) \equiv 0 \pmod{p}$, we can find $b_1$ and $b_2$, both of them $n_1 \pmod{p}$ such that $P(b_1) \equiv 0 \pmod{p^2}$ and $P(b_2) \equiv p \pmod{p^2}$. Notice that, $p \nmid P'(n_1)$ since it is well known that $P(x+pt) \equiv P(x)+ptP'(x) \pmod{p^2}$, but this means that by hensel's lemma, we have a sequence $m_i$ such that $P(m_i) \equiv \{0, p, 2p, \dots, p^2-p\} \pmod{p^2}$ which is a contradiction as we assumed that only $0, 1, \dots, p$ are coverable. If $p=2$, if $a=2$ i.e $n=4$, we can easily check by hand that $d=3$ works. For $a\geq 3$, it just suffices to prove that $n=8$ doesn't work. If $n=8$, consider the set $\{0, 1, 2\}$, there exists $a$ such that $P(a) \equiv 0 \mod{p}$ and there exist $a_1 \equiv a_2 \equiv a \pmod{8}$ such that $P(a_1) \equiv 0 \pmod{8}$ and $P(a_2) \equiv 2 \pmod{8}$ which means $2 \nmid P'(a)$ and we can get a similar contradiction as the odd prime powers case by hensel's lemma. $\blacksquare$

I don't feel like this was that ugly? Maybe that reveals more about me than the problem The answer is $d=n-1$ if $n=4$ or $n$ is prime, and no such $d$ exists otherwise. For $n$ prime, note that $d \leq n-1$ by Lagrange interpolation. On the other hand, by taking $S=\{0,1\}$, since the leading coefficients of each of the degree $n-1$ terms we add together in Lagrange interpolation can be seen to be equal, and we add less than $n$ terms but more than $0$, it follows that any polynomial which "covers" $\{0,1\}$ is degree $n-1$, so this is sharp. For $n=4$, if $S=\{0,1,2,3\}$ then use the identity. If $|S|=1$ then use a constant, if $|S|=2$ use a quadratic (clearly possible) and if $|S|=3$ take a cubic. Furthermore, check that we can't cover $|S|=3$ with a quadratic or less (we can ignore the constant term). Now we prove that nothing else works. Clearly, if $n$ is not $d$-coverable for any $d$, then no multiples of $n$ are either. Therefore, it suffices to show that $n$ with at least $2$ prime divisors, $n=p^2$ where $p$ is an odd prime, and $n=8$ all fail. If we can write $n=ab$ where $\gcd(a,b)=1$, then take $S=\{0,a,b\}$. If this is coverable by some polynomial $P$, there must exist some $1 \leq x \leq a$ such that $P(x) \equiv b \pmod{a}$, so then for any integer $k$, $P(x+ka) \equiv b \pmod{a} \implies P(x+ka) \equiv b \pmod{n} \implies P(x+ka) \equiv b \pmod{b}$. Since $x+ka$ is surjective modulo $b$, it follows that $b \mid P(x)$ for all integers $x$, but then no $x$ exist with $P(x) \equiv a \pmod{n}$: contradiction. For $n=p^2$ where $p$ is an odd prime, take $S$ to be the subset of all numbers not divisible by $p$, as well as $0$ and $p$. Suppose that this was coverable by some polynomial $P$. Since $P$ is surjective modulo $p$, it must be injective, so it has exactly one root modulo $p$, say $r$. Then by Hensel lifting, if $P'(r) \equiv 0 \pmod{p}$ then for any integer $k$, we have $P(r) \equiv P(r+kp) \pmod{p^2}$, and otherwise $P(r+kp)$ is surjective modulo $p^2$, but both cases contradict our choice of $S$. For $n=8$, take $S=\{0,1,2,3,5,6,7\}$. This case is somewhat similar to before. Suppose that this was coverable, so there is exactly one root of $P$ modulo $2$, say $r$. Suppose WLOG that $P(r) \equiv 0 \pmod{4}$, but $P(r+2) \equiv 2 \pmod{4}$. If $P'(r+2) \equiv 0 \pmod{2}$, then by Hensel lifting $P(r+2) \equiv P(r+6) \pmod{8}$, but this means that $2$ and $6$ cannot simultaneously be covered. If $P'(r) \equiv 1 \pmod{2}$, then by Hensel lifting $P(r) \not \equiv P(r+4) \pmod{4}$, but this contradicts the fact that only $0$ is covered and not $4$. However, since $P'(r) \equiv P'(r+2) \pmod{2}$, these two cases cover all possibilities, so $n=8$ fails. Therefore we are done. $\blacksquare$ Ok yeah it was pretty ugly