How can I solve this quantum mechanical "paradox"?

This is what happens if one cares not for the subtlety that quantum mechanical operators are typically only defined on subspaces of the full Hilbert space.

Let's set $a=1$ for convenience. The operator $p =-\mathrm{i}\hbar\partial_x$ acting on wavefunctions with periodic boundary conditions defined on $D(p) = \{\psi\in L^2([0,1])\mid \psi(0)=\psi(1)\land \psi'\in L^2([0,1])\}$ is self-adjoint, that is, on the domain of definition of $p$, we have $p=p^\dagger$, and $p^\dagger$ admits the same domain of definition. The self-adjointness of $p$ follows from the periodic boundary conditions killing the surface terms that appear in the $L^2$ inner product $$\langle \phi,p\psi\rangle - \langle p^\dagger \phi,\psi\rangle = \int\overline{\phi(x)}\mathrm{i}\hbar\partial_x\psi(x) - \overline{\mathrm{i}\hbar\partial_x\phi(x)}\psi(x) = 0$$ for every $\psi\in D(p)$ and every $\phi\in D(p^\dagger) = D(p)$, but not for $\phi$ with $\phi(0)\neq\phi(1)$.

Now, for the question of the commutator: the multplication operator $x$ is defined on the entire Hilbert space, since for $\psi\in L^2([0,1])$ $x\psi$ is also square-integrable. For the product of two operators $A,B$, we have the rule $$ D(AB) = \{\psi\in D(B)\mid B\psi\in D(A)\}$$ and $$ D(A+B) = D(A)\cap D(B)$$ so we obtain \begin{align} D(px) & = \{\psi\in L^2([0,1])\mid x\psi\in D(p)\} \\ D(xp) & = D(p) \end{align} and $x\psi\in D(p)$ means $0\cdot \psi(0) = 1\cdot\psi(1)$, that is, $\psi(1) = 0$. Hence we have $$ D(px) = \{\psi\in L^2([0,1])\mid \psi'\in L^2([0,1]) \land \psi(1) = 0\}$$ and finally $$ D([x,p]) = D(xp)\cap D(px) = \{\psi\in L^2([0,1])\mid \psi'\in L^2([0,1])\land \psi(0)=\psi(1) = 0\}$$ meaning the plane waves $\psi_{p_0}$ do not belong to the domain of definition of the commutator $[x,p]$ and you cannot apply the naive uncertainty principle to them. However, for self-adjoint operators $A,B$, you may rewrite the uncertainty principle as $$ \sigma_\psi(A)\sigma_\psi(B)\geq \frac{1}{2} \lvert \langle \psi,\mathrm{i}[A,B]\rangle\psi\rvert = \frac{1}{2}\lvert\mathrm{i}\left(\langle A\psi,B\psi\rangle - \langle B\psi,A\psi\rangle\right)\rvert$$ where the r.h.s. and l.h.s. are now both defined on $D(A)\cap D(B)$. Applying this version to the plane waves yields no contradiction.

Notice that $\psi(x)$ is defined on a circle of circumference $a$. Multiplying $x$ on this circle is really multiplying a periodic extension of $x$, i.e., the sawtooth function $x - a\lfloor x/a\rfloor$, where $\lfloor y\rfloor$ means the largest integer not greater than $y$. So, the commutator of the position and momentum operators involves the derivative of not only $x$ but also the discontinuous part $-a\lfloor x/a\rfloor$. Therefore, \begin{equation} \sigma_{x} \sigma_p \geq \frac{1}{2}\Big|\langle \psi|\,[\hat{x},\hat{p}]\,|\psi\rangle\Big| = \frac{\hbar}{2}\Bigg|\Big\langle\psi\,\Big|\frac{d}{dx}\big(x - a\lfloor x/a\rfloor\big)\Big|\,\psi\Big\rangle\Bigg| = \frac{\hbar}{2}\Big|1-a|\psi(0)|^{2}\Big|. \end{equation} For a plane wave $\psi(x) = e^{ikx}/\sqrt{a}$, the above reduces to $\sigma_{x} \sigma_p\ge0$, as desired.