Why is $p_y$ conserved in the Landau gauge when we know the electron moves in circles?

It's important to note that none of this is specific to quantum mechanics, and that you get exactly the same structure for the corresponding problem within classical hamiltonian mechanics.

There, you have the hamiltonian $$ H=\frac{1}{2m}p_x^2 + \frac{1}{2m}\left(p_y -\frac{eB}{c}x \right)^2, $$ which naturally conserves $p_y$ since $y$ does not appear in $H$ and therefore $\{p_y,H\}=0$. To see what's going on, it helps to write out Hamilton's equations explicitly: \begin{align} \dot x & = \frac{\partial H}{\partial p_x} = \frac{p_x}{m} \\ \dot p_x & = -\frac{\partial H}{\partial x} = \frac{eB}{mc}\left(p_y-\frac{eB}{c}x\right) \\ \dot y & = \frac{\partial H}{\partial p_y} = \frac{p_y-\tfrac{eB}{c}x}{m} \\ \dot p_y & = -\frac{\partial H}{\partial y} = 0. \end{align}

Here you get the same structure as in quantum mechanics: the canonical momentum $p_y$ is conserved, but it differs from the kinematic momentum $m\dot y = p_y-\tfrac{eB}{c}x$, which is obviously not conserved (as opposed, in particular, to what you stated in a comment.

That said, it is indeed very odd, at least at first glance, that you can change which component of the canonical momentum is conserved and which one isn't using just a gauge transformation. Since the gauge transformation isn't physical (i.e. it's just in our heads) this does look very odd; however, it's important to note that canonical momentum is also a quantity that's just in our heads, so there isn't that much of a paradox.

Digging down a bit deeper, though, it is intuitively obvious that there should be two independent constants of the motion, and with a bit of work one can see that this is indeed the case. Leaving the canonical momenta out of the picture for a moment, these two constants of the motion are given by $$ x_0= x+\frac{mc}{eB}v_y \quad\text{and}\quad y_0 =y-\frac{m c}{eB}v_x. $$ It is easy to verify manually from the equations of motion that these two quantities are conserved. Moreover, using this conservation property, their two definitions above can be easily rephrased in the form \begin{align} \frac{\mathrm d}{\mathrm dt}(y-y_0) & = -\tfrac{eB}{mx}(x-x_0) \\ \frac{\mathrm d}{\mathrm dt}(x-x_0) & = +\tfrac{eB}{mx}(y-y_0). \end{align} This is a first-order ODE in $(x-x_0,y-y_0)$, which is easily solved to show that $(x,y)$ circles about $(x_0,y_0)$; that is, the conserved quantity $(x_0,y_0)$ is the centre of the particle's circular motion.

The reason the Landau gauge has a conserved canonical momentum $p_y$ is that it manages to align one of its canonical momentum axes with one of these conserved quantities, and indeed it's just a bit of algebra to show that $$p_y = \frac{eB}{c} x_0.$$ Of course, in the process you lose the direct relationship between the canonical and the kinematic momentum - and no amount of gauge changing will make the kinematic momentum, which is a physical quantity, be conserved.

Finally, to comment a bit on the quantum mechanical side of the problem, it's important to note that while it looks like you can set $p_y$ to be arbitrarily large, thus giving the electron more and more velocity in a regime where it should just be moving in circles, this is not actually the case. In the standard way to solve this, you simply look for eigenstates of $\hat H$ which are also eigenstates of the canonical momentum $\hat p_y = -i\hbar \frac{\mathrm d}{\mathrm dy}$ (i.e. plane waves along $y$), and then you look at the $x$ coordinate to get the reduced hamiltonian $$ \hat H = \frac{\hat{p}_x^2}{2m}+\frac{e^2B^2}{2mc^2}(x-x_0)^2. $$ This hamiltonian describes simple harmonic oscillations, about a centre $x_0=\frac{c}{eB}p_y$ given by the eigenvalue $p_y$ of the $y$-direction plane wave. For a fixed hamiltonian eigenvalue, the eigenfunctions are supported in a strip, which can be displaced side-to-side by varying $p_y$.

Here the important point is that the velocity operator is not $\hat{p}_y$ at all; instead, it is ($1/m$ times) the kinematic momentum $m\hat{v}_y = \hat{p}_y -\frac{eB}{c}\hat x$. However big you make $\hat{p}_y$, if you look along the centerline of the strip, the velocity is zero, and it varies symmetrically about it: $v_y$ is negative for $x>x_0$, and vice versa.

Thus, while it is still very much its own, the quantum mechanical 'motion' is a lot more consistent with the classical circling electrons than it looks at first glance.

The short answer is that one must distinguish between the canonical/conjugate momentum $\hat{p}_{\mu}$ and the kinetic/mechanical momentum $m\hat{v}_{\mu} ~=~ \hat{p}_{\mu} - qA_{\mu}(\hat{x})$, cf. e.g. this post.