I found the solution (with the help of a friend: cudos!). The posterior is
$$\begin{align*}
-\log p(\boldsymbol{w}|\boldsymbol{x}) &= -\log p(\boldsymbol{x}|\boldsymbol{w}) - \log p(\boldsymbol{w}) + \text{const.} \\
&= \sum\limits_j \log \left( 1 + \exp(-y_j \boldsymbol{w}^\top \boldsymbol{x}_j) \right) + \sum\limits_i \frac{q_i (w_i - m_i)^2}{2} + \text{const.}'
\end{align*}$$
where the constant terms do not depend on $\boldsymbol{w}$, and with the NLL
$$\begin{align*}
-\log p(\boldsymbol{x}|\boldsymbol{w}) &= \sum_j \log \left[ \frac{1 + y_j}{2} \left( 1 + \mathrm{e}^{-\boldsymbol{w}^\top \boldsymbol{x}_j} \right) + \frac{1 - y_j}{2} \left( 1 + \mathrm{e}^{+\boldsymbol{w}^\top \boldsymbol{x}_j} \right) \right] \\
&= \sum\limits_j \log \left( 1 + \mathrm{e}^{-y_j\boldsymbol{w}^\top \boldsymbol{x}_j} \right)
\end{align*}$$
for $y_j = \{-1, +1\}$ **(!)**.
Ignoring correlations, the Laplace approximation then yields
$$\begin{align*}
q_i &\leftarrow - \left. \frac{1}{p(\boldsymbol{\hat w} | \boldsymbol{x})} \frac{\partial^2 p(\boldsymbol{w} | \boldsymbol{x})}{\partial w_i^2} \right|_{\boldsymbol{w} = \boldsymbol{\hat w}} \\
&= \left. -\frac{\partial^2 \log p(\boldsymbol{w} | \boldsymbol{x})}{\partial w_i^2} \right|_{\boldsymbol{w} = \boldsymbol{\hat w}} \\
&= q_i + \sum\limits_j x_{ij}^2 \frac{1}{1 + \mathrm{e}^{-y_j \boldsymbol{\hat w}^\top \boldsymbol{x}_j}} \frac{1}{1 + \mathrm{e}^{+y_j \boldsymbol{\hat w}^\top \boldsymbol{x}_j}} \\
&= q_i + \sum\limits_j x_{ij}^2 \frac{1}{1 + \mathrm{e}^{-\boldsymbol{\hat w}^\top \boldsymbol{x}_j}} \frac{1}{1 + \mathrm{e}^{+\boldsymbol{\hat w}^\top \boldsymbol{x}_j}} \\
&= q_i + \sum\limits_j x_{ij}^2 \, p_j (1-p_j)
\end{align*}$$
with $x_{ij} = (\boldsymbol{x}_j)_i$ and $$\boldsymbol{\hat w} = \underset{\boldsymbol{w}}{\operatorname{argmax}} p(\boldsymbol{x} | \boldsymbol{w}) \,.$$