Why $xx^TM$ requires $O(dk)$ operations?
The matrix $xx^T$ has the $(i,j)$th entry $x_i x_j$. Hence
$$
(xx^TM)_{ij} = \sum_k (xx^T)_{ik} M_{kj} = \sum_k x_i x_k M_{kj} = x_i \sum_k x_k M_{kj}.
$$
We can compute $\sum_k x_k M_{kj}$ for each $j$ in linear time. Given that, we can compute the product matrix in linear time using the above formula.