Upper bound on answer for Pell equation

Let $d$ be a positive fundamental discriminant, $\epsilon_d$ denote the fundamental unit, $h(d)$ the class number, and $\chi_d$ the primitive character associated to the discriminant $d$. The class number formula gives $$ \log \epsilon_d = \sqrt{d} L(1,\chi_d)/h(d) \le \sqrt{d} L(1,\chi_d), $$ since the class number $h(d) \ge 1$. Now it is known that $L(1,\chi_d) \le C \log d$ for a constant $C$. This upper bound is completely effective. The best known constant $C$ is (for large enough $d$) $$ \frac{1}{4} \Big(2-\frac{2}{\sqrt{e}} \Big). $$ If we knew something about how small primes split in ${\Bbb Q}(\sqrt{d})$ then this could be improved by taking those Euler factors into account (for example, we can use this if $d$ is even which would happen for primes $p\equiv 3\pmod 4$ in the question). This is a result of P.J. Stephens and uses the Burgess bound for character sums (together with an argument from multiplicative number theory along the lines of Vinogradov's $1/\sqrt{e}$ argument for the least quadratic non-residue). For a discussion of Stephens's result and extensions, see Granville and Soundararajan.
This would be enough to give your conjecture of $p^{C\sqrt{p}}$ (one needs a little care to go from the fundamental unit to the solution to Pell's equation -- i.e. one might need to take a small power of the fundamental unit). Also see this paper of Hua which explicitly states a bound along the lines you want, tracing it back to Schur. Finally, Louboutin has looked at explicit upper bounds for $L(1,\chi)$ (see Theorem 5.1 there).

The above results are unconditional. On GRH one can do a bit better, since $L(1,\chi_d)$ may then be bounded by $C\log \log d$, and then one would get a better bound of $(\log p)^{C\sqrt{p}}$ in your problem (see Theorem 1.5 of this paper for an explicit GRH bound), and I think that can probably happen (although this is not clear since we don't know that the class number can get down to $1$). Jacobson, Lukes and Williams report on extensive calculations on regulators, and at the end of the paper state the belief that the fundamental unit can get as large as $\exp(c \sqrt{d}\log \log d)$; however, as also noted there, unconditionally we only know that the fundamental unit (or the solution in Pell's equation) sometimes gets as large as $\exp(c(\log d)^4)$ -- so there is a very large gap in our understanding. (See also my answer to the related MO question Upper bound for class number of a real quadratic field .)

Let $u_0=x_0+y_0\sqrt{p}$ be the smallest solution with $x_0,y_0>0$. (I assume you're talking about an upper bound for the smallest solution, since obviously there are solutions that are arbitrarily large.) Also let $h_p$ denote the class number of the ring of integers of $\mathbb Q(\sqrt p)$. Then Siegel's theorem says that $$ \lim_{p\to\infty} \frac{\log\bigl(h_p\log|u_0|\bigr)}{\log\sqrt p} = 1. $$ So at least approximately, we have $$ |x_0| < |u_0| \approx \exp(\sqrt p/h_p) = p^{{\sqrt p}/{(h_p\log p)}} \le p^{\sqrt p/\log p}. $$ So this is a little better than your conjecture, but it's probably hard to see experimentally that $1/\log p$ in the exponent. And of course, the upper bound gets better as the class number increases, but conjecturally $h_p=1$ infinitely often, so in general one can't do better. Siegel's theorem is ineffective, but it may be that the upper bound you want is effective and the ineffectivity is in the lower bound.