The answer is no, but it's almost yes. A stochastic Turing machine can find a diagonally non-computable ($\textsf{DNC}$) function ($f$ with $f(x)\ne\varphi_x(x)$ for all $x$) and finding a complete extension of PA is equivalent to finding a $\textsf{DNC}$ function with $f(x)\in\{0,1\}$ for all $x$.

Frank Stephan showed that a stochastic TM cannot find any completion of PA. (The fact that it cannot find any *given* one, as in Carl Mummert's answer, was known earlier.)