There many different ways to calculate the MSE, depending on how much you condition on. You are perfectly justified in being confused about what varies and what is fixed. It is always a great source of confusion (perhaps not until I finish my book :)).
The easiest way is to condition on "X"s and let "Y"s vary for both the training and test data.
Let $f^*(x)$ be the true regression function $\mathbb E(Y | X = x)$, where $(X,Y)$ is the test point.
Show that for any fixed function $f$, we have
$$
\mathbb E(Y - f(x))^2 = (f(x) - f^*(x))^2 + \text{var}(Y | X=x)
$$
The second term is what they assume to be constant and represented as $\text{var}(\epsilon)$ in their formula. This is the irreducible error (the Bayes error, or the variance of the optimal rule $f^*$). In the above calculation $Y$ is random but we have conditioned on $X = x$, i.e., the test $X$ is fixed but the test $Y$ is allowed to vary (hence the irreducible term). Let us write $\sigma^2(x) = \text{var}(Y | X=x)$ for simplicity.
Next, we can apply the above to an estimate $\hat f$, if we condition on the entire training data $D_n = \{(X_i,Y_i)\}_{i=1}^n$ to make $\hat f$ fixed. We obtain
$$
\mathbb E[ (Y - \hat f(x))^2 | D_n] = (\hat f(x) - f^*(x))^2 + \sigma^2(x). \quad (*)
$$
Next, let us evaluate the first term, but average over the training "Y"s while keeping training "X"s fixed. Let $X^n = (X_1,\dots,X_n)$ collect the training $X$s. Show that
$$
\mathbb E [(\hat f(x) - f^*(x))^2 | X^n] =
\bigl(\mathbb E[\hat f(x) | X^n] - f^*(x)\bigr)^2 + \text{var}\bigl(\hat f(x) |X^n\bigr). \quad (**)
$$
Here, the variation/randomness is that of training "Y"s while training "X"s are kept fixed. This version is good enough to study bias-variance decomposition, and I suggest you stop here.
If you must, you can start averaging out over more. For example, since $\mathbb E[ \,\mathbb E[Z | D_n] \,| X^n] = \mathbb E [Z | X^n]$ (why?) Taking $\mathbb E[\cdots |X^n]$ of both sides of (*) and combining with (**) you get
$$
\mathbb E_n [(Y - \hat f(x))^2] =
\bigl(\mathbb E_n[\hat f(x)] - f^*(x)\bigr)^2 + \text{var}_n\bigl(\hat f(x) \bigr) + \sigma^2(x). \quad (**)
$$
where I am writing $\mathbb E_n$ to denote $\mathbb E[\cdots |X^n]$ for simplicity and similarly for the variance.
If you must, you can go further. You can take the expectation of both sides to average out the effect of $X^n$. You can even replace $x$ with random $X$ and average over that as well (so far everything was conditioned on that). By the smoothing property of conditional expectation, the left-hand side would be unconditional expectation over every source of randomness. The right-hand side though remains a mess:
$$
\mathbb E [(Y - \hat f(X))^2] =
\mathbb E\bigl[ \bigl(\mathbb E_n[\hat f(X)] - f^*(X)\bigr)^2 \bigr] + \mathbb E \bigl[ \text{var}_n\bigl(\hat f(X) \bigr) \bigr] + \mathbb E[ \sigma^2(X)]. \quad (**)
$$
They can't put that in a book without scaring people off. It is also questionable whether you want this much averaging over everything.
The short answer is, their expression is not quite accurate, or rather they are hiding things in the bias term and what the variance is with respect to. In general they are not being explicit about what they are averaging over.
The comment about averaging over many training data you can interpret as trying to interpret what expectation means from a frequentist perspective. It is always for a fixed "n", the same "n" as your original data.