Perfect Probabilistic Encryption still requires key length about as long as message
It seems you have to use some different approach. There is a hint in Arora/Barak's book. From that hint, I got the following solution.

Again we set $x_0=0^{n+10}$. The algorithm $A$ works as follows. Let $y=E_k(x_b)$ be its input. Let $Y_{x_1}$ denote the set of ciphtertexts $y$ such that there exists some $k$ satisfying $D_k(y)=x_1$ ($D$ is the decryption algorithm). The algorithm $A$ outputs $1$ if and only if $y\in Y_{x_1}$ (so $A$ runs in polynomial time if P = NP). Then we have

$$\mathrm{Pr}_{b \in \{0,1\}, k \in \{0,1\}^n}[A(E_k(x_b)) = b ]=\frac{1}{2}\left(1-\mathrm{Pr}_{k\in\{0,1\}^n}[E_k(x_0)\in Y_{x_1}]\right)+\frac{1}{2}.$$

If this probability is less than $9/10$ for all $x_1\in \{0,1\}^{n+10}$, then we have $\mathrm{Pr}_{k\in\{0,1\}^n}[E_k(x_0)\in Y_{x_1}]&gt;1/5$. This means $\mathrm{Pr}_{k\in\{0,1\}^n,k'\in\{0,1\}^n}[D_{k'}(E_k(x_0))=x_1]&gt;2^{-n}/5$. Note this inequality holds for all $x_1\in \{0,1\}^{n+10}$, which means

\begin{align}
1&amp;=\mathrm{Pr}_{k\in\{0,1\}^n,k'\in\{0,1\}^n}[D_{k'}(E_k(x_0))\in\{0,1\}^{n+10}]\\
&amp;=\sum_{x_1\in\{0,1\}^{n+10}}\mathrm{Pr}_{k\in\{0,1\}^n,k'\in\{0,1\}^n}[D_{k'}(E_k(x_0))=x_1]\\
&amp;&gt;\frac{2^{n+10}\cdot2^{-n}}{5},
\end{align}

a contradiction!