How can I resolve this basic MAC paradox I’m stumbling upon in my proof?
Your attack on $S$ involves computing $S'(k,m_i)$ for arbitrary messages $m_1,\dots,m_q$. In order to do that, you must compute $S(k,m_i)$ and $S(k,0^n)$, and thus you have obtained $S(k,0^n)$. This means that $0^n$ must be added to the list of invalid forgeries, and so in order to present a valid forgery for $S$, you must have
$$(m,S(k,m)) \notin \{(0^n,S(k,0^n),(m_1,S(k,m_1)),\dots,(m_q,S(k,m_q))\}.$$

But you do not know how to do that: the only known attack on $S'$ precisely involves computing $S(k,0^n)$. More precisely, the attack goes like this:


Compute $S'(k,m)$ for some $m \ne 0^n$.
Output $(0^n, (s,s))$ as a forgery for $S'$ (where $s = S(k,0^n)$).


Then, you present $(0^n, s)$ as a forgery for $S$, but this is not a valid one.

The exact point where this error manifests itself in your proof is when you write


  because $(m,S(k,m))$ being an element in that set would contradict (*).


This assumes that if $(m,S(k,m))$ is in the second set, that necessarily means that $(m,S'(k,m))$ is in the first one. In other words, that if a "request" for $S(k,m)$ was made, it necessarily means that a request for $S'(k,m)$ was made as well. This is, again, not correct: it is possible to make a request for $S(k,0^n)$ without making one for $S'(k,0^n)$.