OK, having spent about 20 hours on the search of a nice proof (which extinguished my passion for beauty for the next several days at least), I'm resorting to the brute force. I will love to see someone else to avenge this pitiful defeat of mine...
As I mentioned in the comment, the key to the solution is the inequality
$$
(1+a)\log(1+b)+(1+b)\log(1+a)\ge 2(1+c)\log(1+c)
$$
where $a,b,c>0, ab=c^2$.
Consider the function
$$
F(t)=(1+a)\log(1+bt)+(1+b)\log(1+at)-2(1+c)\log(1+ct)\,.
$$
We have
$$
\begin{aligned}
F'(t)&=\frac{(1+a)b}{1+bt}+\frac{(1+b)a}{1+at}-2\frac{(1+c)c}{1+ct}
\\
&=(a+b-2c)\frac{(c^2t-1)(ct-1)}{(1+at)(1+bt)(1+ct)}
\end{aligned}
$$
While the derivation of the last equality is tedious, to check it, it suffices to show that $F'(c^{-2})=F'(c^{-1})=0$ and to compute the free term in the numerator to get the right normalization factor, so I'll skip the explicit computations.
It will be convenient to denote $p=c^{-1}$. Then we need to show that
$$
\int_0^1\frac{(t-p^2)(t-p)}{(1+at)(1+bt)(1+ct)}\,dt\ge 0\,.
$$
If $p>1$, there is nothing to do because the integrand is non-negative. So, we'll assume that $p<1$ from now on.
Since the denominator is increasing in $t$, and the numerator is positive on $(0,p^2)$, negative on $(p^2,p)$ and then positive again on $(p,1)$, we would be in good shape if we had
$$
\int_0^p(t-p^2)(t-p)\,dt=-\frac{p^3}6+\frac{p^4}2\ge 0\,,
$$
which is true for $p\ge \frac 13$. Thus, we may assume that $p<\frac 13$.
Now we cannot just neglect the interval $[p,1]$. We shall neglect the interval $[0,p^2]$ instead. Assuming $a\ge c\ge b$, we write
$$
\begin{multline}
\int_{p^2}^p\frac{(t-p^2)(t-p)}{(1+at)(1+bt)(1+ct)}\,dt=
\int_p^1\frac{(t-p)(t-1)p^2}{(p^{-1}+at)(1+bpt)(1+cpt)}\,dt
\\
\ge
\int_p^1\frac{(t-p)(t-1)p^2}{(1+at)(1+bpt)(1+t)}\,dt
\end{multline}
$$
Combining this with $\int_p^1$, we get the lower bound
$$
\int_p^1\frac{(t-p)}{(1+at)}\left[\frac{(t-1)p^2}{(1+bpt)(1+t)}
+\frac{t-p^2}{(1+bt)(1+ct)}\right]\,dt
$$
Note now that $bp\le 1$ and the higher $b$ is, the harder it is for the last square bracket to be non-negative. Thus, it is enough to estimate the bracket for $bp=1$, i.e., to demonstrate that
$$
(1-t)(p+t)^2\le (t-p^2)(1+t)^2\,.
$$
However
$$
t-p^2\ge t(1-t)
$$
and
$$
(p+t)^2=2pt+p^2+t^2<t+2t^2<t(1+t)^2\,.
$$
I would appreciate it if someone checks this ugly monster before I post the remaining (almost trivial) part of the proof :).
Edit: Assuming that those who upvoted took trouble to read and verify the above part, the end is as follows.
Let $X=X_j$, $Y=Y_j$, and $K$ be as before. Then, as I said, $\sqrt{XY}\le K\le\sqrt{XY}+\sqrt{(1-X)(1-Y)}$ (Cauchy). We have $Z=Z_j=\frac{\sqrt{XY}}K$, so it will suffice to show that
$$
2K^2 Z\log\frac 1Z=2K\sqrt{XY}\log\frac{K}{\sqrt{XY}}\le X\log\frac 1X+Y\log\frac 1Y\,.
$$
Note that the left hand side is convex in $K$ for fixed $X,Y$. If $K=\sqrt{XY}$, the inequality is trivial ($0$ is less than or equal to a non-negative number). Thus, we need only consider the case $K=\sqrt{XY}+\sqrt{(1-X)(1-Y)}$. Dividing by $XY$ and putting $X^{-1}=1+x, Y^{-1}=1+y$, so that $\frac{1-X}X=x,\frac{1-Y}Y=y$, we see that this case reduces exactly to the above inequality.
P.S. There is an alternative proof of the main inequality on AoPS. Alas, it also requires some tedious computations...
Best Answer
First, let us do some cleaning here.
Thus, the corrected version of your inequality in question is this: $$E_\rho F-\ln E_\pi e^F\le E_\pi Y\ln Y$$ or, equivalently, $$E_\pi YF-\ln E_\pi e^F\le E_\pi Y\ln Y. \tag{1}$$
Since $E_\pi Y=1$, the left-hand side of (1) will not change if $F$ is replaced by $F-c$, for any real constant $c$. So, without loss of generality $E_\pi e^F=1$, and then (1) becomes $$E_\pi YF\le E_\pi Y\ln Y. \tag{2}$$ By convexity,
$$e^F\ge e^u+(F-u)e^u$$ for all real $u$. Substituting here $u=\ln Y$ and taking the expectations, we get $$E_\pi Y=1=E_\pi e^F\ge E_\pi Y+E_\pi (F-\ln Y)Y,$$ so that (2) follows.
So, (0) holds, as desired.
Of course, (0) will continue to hold with $K(\rho,\pi)$ in place of $D_{KL}(\rho\mid\pi)$, because the symmetrized KL information $K(\rho,\pi)$ is no less than the standard KL information $D_{KL}(\rho\mid\pi)$.