What I am missing in this simple equation from Nesterov's paper?

The author is correct. The norm in question is induced by the real inner product $(x,y):=\langle Bx,y\rangle$ where $B$ is positive definite with respect to $\langle\cdot,\cdot\rangle$. Let $u = x_{k+1} - x^\ast$ and $v = x_{k+1}-x_k$. Then the equation is simply saying that $$ \|u\|^2 = \|u-v\|^2 + 2(v,u) - \|v\|^2, $$ which is just a rearrangement of terms in the cosine law $$ \|u-v\|^2 = \|u\|^2 - 2(v,u) + \|v\|^2. $$

If it is bilinear, the derivation is correct.

$$2\langle B(x_{k+1}-x_k),x_k-x^*\rangle +\Vert x_{k+1}-x_k\Vert^2=$$

$$=2\langle B(x_{k+1}-x_k),x_k-x^*\rangle +2\Vert x_{k+1}-x_k\Vert ^2-\Vert x_{k+1}-x_k\Vert^2=$$

$$=2\left(\langle B(x_{k+1}-x_k),x_k-x^*\rangle +\langle B(x_{k+1}-x_k),x_{k+1}-x_k\rangle\right)-\Vert x_{k+1}-x_k\Vert^2=$$

$$=2\langle B(x_{k+1}-x_k),x_k-x^*+x_{k+1}-x_k\rangle -\Vert x_{k+1}-x_k\Vert^2=$$

$$=2\langle B(x_{k+1}-x_k),x_{k+1}-x^*\rangle -\Vert x_{k+1}-x_k\Vert^2$$