It is not possible. We can consider the simpler case of constructing $C^3(U)$ using only $\tt{CNOT}$, Toffoli, $U$, $V$, $C(U)$, $C^2(U)$ and $C(V)$ where $V^2=1$.
We consider the determinant of the matrix representation of the gates over only the first 3 qubits (so the outcome of the determinant is an operator on the last qubit), and we have:
$$
C^3(U)
= \left.\begin{array}{ccc}- & \bullet & - \\ & | & \\- & \bullet & - \\ & | & \\- & \bullet & - \\ & | & \\- & U & -\end{array}\right.
= \left(\begin{array}{cccccccc}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\0 & 0 & 0 & 0 & 0 & 0 & 0 & U\end{array}\right)
\Rightarrow \det C^3(U) = U
$$
$$
C^2(U)
= \begin{array}{ccc}- & - & - \\ & & \\- & \bullet & - \\ & | & \\- & \bullet & - \\ & | & \\- & U & -\end{array}
= \left(\begin{array}{cccccccc}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\0 & 0 & 0 & U & 0 & 0 & 0 & 0 \\0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\0 & 0 & 0 & 0 & 0 & 0 & 0 & U\end{array}\right)
\Rightarrow \det C^2(U) = U^2
$$
$$
C(U)
= \left.\begin{array}{ccc}- & - & - \\ & & \\- & - & - \\ & & \\- & \bullet & - \\ & | & \\- & U & -\end{array}\right.
= \left(\begin{array}{cccccccc}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\0 & U & 0 & 0 & 0 & 0 & 0 & 0 \\0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\0 & 0 & 0 & U & 0 & 0 & 0 & 0 \\0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\0 & 0 & 0 & 0 & 0 & U & 0 & 0 \\0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\0 & 0 & 0 & 0 & 0 & 0 & 0 & U\end{array}\right)
\Rightarrow \det C(U) = U^4
$$
$$
U
= \begin{array}{ccc}- & - & - \\ & & \\- & - & - \\ & & \\- & - & - \\ & & \\- & U & -\end{array}
= \left(\begin{array}{cccccccc}U & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\0 & U & 0 & 0 & 0 & 0 & 0 & 0 \\0 & 0 & U & 0 & 0 & 0 & 0 & 0 \\0 & 0 & 0 & U & 0 & 0 & 0 & 0 \\0 & 0 & 0 & 0 & U & 0 & 0 & 0 \\0 & 0 & 0 & 0 & 0 & U & 0 & 0 \\0 & 0 & 0 & 0 & 0 & 0 & U & 0 \\0 & 0 & 0 & 0 & 0 & 0 & 0 & U\end{array}\right)
\Rightarrow \det U = U^8
$$
Similarly, we can prove $\det V = V^8 = U^4$ and $\det C(V) = V^4 = U^2$.
The determinant of $\tt{CNOT}$ and Toffoli do not involve factors of $U$ so they will not affect the analysis below.
Now suppose $C^3(U)$ can be constructed by the combinations $C^3(U) = G_1 G_2 \cdots$, where each $G_i$ is among the gates stated above, then we must have:
$$
\det C^3(U) = \prod_i \det G_i \Rightarrow \prod_i \det G_i = U
$$
This identity is however impossible to satisfy using the gates above because the determinants of $U$, $V$, $C(U)$, $C^2(U)$ and $C(V)$ all give even powers of $U$.
The only possible way out is to include $C(\sqrt{V})$ because $\det C(\sqrt{V})=\sqrt{V}^4= U$. But $C(\sqrt{V})$ can be used to construct $C^2(V)$. If we can use $C^2(V)$, then the solution to (4.28) is rather obvious and we get the solution given by Bram.
The proof for more qubits is similar.
I am a physicist, not specialized in quantum computing. Question 4.28 was indeed frustrating. Up until that question, the underlying principle of the chapter was the construction of more complicated gates using more elementary gates. Had I known the authors wanted us to use $C^2(V)$ (which would require $C(\sqrt{V})$ gate, which may or may not exist, not previously constructed nor alluded to in the question), I would have solved the question in less than a minute. Perhaps proving once and for all there is no solution (the way most readers would interpret the question) will save others from the frustration.
