Let $p$ be prime and $0Let $p$ be prime and $0<a< p$ an integer such that $$ \Big({a\over p}\Big) =1$$
Then there exists integers $x,y$ such that $p=x^2-ay^2$.

Edit: For which primes is this true? From CalebKoch answer we see this is not true in general. Can you sugest me a literature where I can find a theory of this.
I suspect, if it is true, then it has something to do with a Thue theorem. http://mathworld.wolfram.com/ThuesTheorem.html
A found this interesting results:
https://en.m.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_two_squares
 A: I don't think this is true. Consider the following counter example: let $p=11$ and $a=3$. Then $a$ is a quadratic residue mod $p$ since $3\equiv 5^2\pmod{11}$. Consider then the equation $11=x^2-3y^2$. Taking this modulo 3 gives $2\equiv x^2 \pmod{3}$. No such $x$ exists so the equation cannot be satisfied.
A: Your problem is realated to the factorization of primes in the order $\mathbb Z[\sqrt{a}]$ and class fields of real quadratic fields. 
I think the following is true but you should check it out as I am  not an expert: If $\left({a\over p}\right)=1$  and $z$ is such that $p \mid z^2 -a$ and $p^2\nmid z^2-a$, then consider the ideal $ \mathfrak p = (p,z+\sqrt{a})$, if $\mathfrak p$ is principal then at least one of the equations 
$$ \pm p = x^2-ay^2 $$
has solution, possibly both. Otherwise none of these equations has solution. 
I believe that even determining if a solution with positive sign exists when a solution exists is a very dificult problem.
I also believe that finding a simple characterization of which primes are repreentable is very difficult in general. It mostly depends on $a$, if the real field $Q(\sqrt{a})$ has class number 1 and the norm of it's fundamental unit is $-1$ then every prime with $\left({a\over p}\right)=1$ will be representable in the form $p=x^2-ay^2$. 
I think it is easier and better known the parallel problem for imaginary quadratic fields, ie represent primes as $p= x^2+ay^2$ when $\left({-a \over p}\right) = 1$. For this problem I strongly recommend you the wonderful book Primes of the Form $x^2+ny^2$: Fermat, Class Field Theory, and Complex Multiplication By David A. Cox. You'll get a very good idea of what is involved in your problem!
