Effective algorithm of searching the "nearest" doubly stochastic matrix
This is a special case of the following problem: given a polytope $P$ specified by linear constraints and a point $x$ find $y \in P$ that minimizes $\|x - y\|_2^2$. 

If you are ok with a small additive approximation to $\|x - y\|_2^2$, you can try using the Frank-Wolfe algorithm. This is a sort of gradient descent algorithm. You start from a point $y_0 \in P$ (in your case this could be say the $n \times n$ matrix with $1/n$ in every coordinate) and in each steps you compute $y_{i+1}$ from $y_i$ as follows:


Let $w = x - y_i$.
Let $v$ be the vertex of $P$ that maximizes $w^Tz$ for $z \in P$ (can be found by LP).
Find the point on the line through $y_i$ and $v$ that is closest to $x$ (this is quadratic optimization in a single variable). This point is $y_{i+1}$.


Ken Clarkson has analyzed this simple algorithm. In $t$ steps, the additive approximation is bounded by $d(P)^2/t$, where $d(P)$ is the diameter of $P$. In your case, I believe $d(P) \leq \sqrt{n}$, as the vertices of $P$ are permutation matrices and they all have Frobenius norm $\sqrt{n}$. So in $O(n/\epsilon)$ iterations of the above algorithm you can get $Q$ such that  $\|D - Q\|_F^2 \leq \|D - Q^*\|_F^2 + \epsilon$, where $Q^*$ is the optimal solution.