The binomial formula and the value of $0^0$
I think you do not interpret the text as it was intended. What Knuth is saying is that the binomial formula as stated cannot be valid unless one defines $0^0=1$. He says so more clearly in his 1992 article Two notes on notation (page 6, equation (1.18)):
Anybody who wants the binomial theorem $$(x + y)^n =\sum_{k=0}^n\binom nk x^ky^{n−k}$$ to hold for at least one nonnegative integer $n$ must believe that $0^0 = 1$, for we can plug in $x = 0$ and $y = 1$ to get $1$ on the left and $0^0$ on the right.
Indeed one has for instance $1=(0+1)^2=\binom20.0^0.1^2+\binom21.0^1.1^1+\binom22.0^2.1^0$, and the right hand side reduces to $0^0$ because the last two terms vanish because of the non-controversial evaluations $0^1=0^2=0$.
So in particular, this does not just involve the case of the binomial theorem for exponent$~0$; the point is that exponents$~0$ occur on the in the right hand side for every instance of the binomial formula.
Note that one usually does not encounter this case explicitly because of our habit of contracting the term $\binom n0x^0y^n$ to $y^n$ whenever we write explicit instances of the binomial formula. Your citation illustrates this, as Knuth writes terms $x^4$ and $y^4$ in his explicit instance of the binomial formula for $r=4$. (It also illustrates another common peculiarity: in explicit instances of the binomial formula we tend to take the summation index decreasing from $n$ to $0$, or what amounts to the same use a variant of the formula in which the exponents of $x$ and $y$ are interchanged.)
Indeed, the most important reason we are not confronted with instances of $0^0$ (and therefore with the need to have it well defined) all the time is, that we have learned the habit, similar to that of suppressing explicit terms$~0$ in a summation or factors$~1$ in a product, of immediately replacing any expression $x^0$ by$~1$ (or simply omitting it if occurring in a product). I consider this a nice paradox of human psychology:
The fact that people can maintain that $0^0$ should be left undefined depends on the circumstance that instances of the expression almost never occur when doing mathematics. This state of affairs is a consequence of the habit of systematically suppressing multiplicative factors of the form$~x^0$ when writing formulas. This notwithstanding the fact that the equation $x^0=1$ implicitly applied during this suppression can only be justified if $x^0$ is always defined, in particular for $x=0$.
To the best of my knowledge, the convention that $0^0$ is undefined serves one purpose, namely to avoid a discontinuity of the function $x\mapsto 0^x$ at $0$ (or the function $x^y$ at $(0,0)$). This has value when people (primarily calculus students) think that limits like $\lim_{t\to a}f(t)^{g(t)}$ should be evaluated by plugging $a$ in place of $t$ in $f(t)^{g(t)}$. A discontinuity will cause this method to give the wrong answer when the plugging-in gives $0^0$. Ideally, our calculus students would learn that you have to ascertain continuity before using the plug-in method. In our non-ideal world, a good number of them don't learn that, and so we teach them that $0^0$ is undefined. That way, the result of plugging in will not give them a wrong answer; it will refuse to give them an answer, so it will force them to do something better than plugging in (e.g., take logarithms and try L'Hopital's rule).
But I think the "undefined" convention is useful only for people who might (unknowingly) assume continuity where there is in fact a discontinuity. For the rest of us, $0^0$ should be $1$.
Note, by the way, that the point of discontinuity is at the edge of the domain of definition of $0^y$ (or $x^y$), so it's not particularly surprising (to me) that something strange, from the point of view of analysis, happens there.
EDIT
If $0^0$ assumed to be undefined and empty sums (those with a lower limit greater than upper limit) are assumed to be zero, use:
$(x+y)^n =x^n + \sum_{k=1}^{n-1} (_k^n)x^k y^{n-k} +y^n~~~~~$ for $n\ge 1$
$~~~~~~~~~~~~~~= 1~~~~~~~~~~~~$ for $n=0$ and $x+y\ne 0\\$
If both $0^0$ and empty sums are assumed to be undefined, use:
$(x+y)^n =x^n + \sum_{k=1}^{n-1} (_k^n)x^k y^{n-k} +y^n~~~~~$ for $n\gt 1$
$~~~~~~~~~~~~~~= x+y~~~~~$ for $n=1$
$~~~~~~~~~~~~~~= 1~~~~~~~~~~~~$ for $n=0$ and $x+y\ne 0$
Results in both cases will be consistent with the standard formula except for $(x+y)^0$ being undefined when $x+y=0$.