$p\in\mathbb P\iff\Big(2\leq k<\sqrt p\implies\gcd(k^2,p-k^2)=1\Big ),\;p>3$ This is sharper variant of 
A condition for being a prime: $\;\forall m,n\in\mathbb Z^+\!:\,p=m+n\implies \gcd(m,n)=1$
It seems enough to test that for some sums: 
$p=m+n\implies\gcd(m,n)=1$, namely for the pairs
$(k^2,p-k^2),\; 2\leq k < \sqrt p\;$.
Verified for $3<p<10000$.

Comment:
This algorithm can be used as a fancy integer factoring program, since 
$\gcd(k^2,p-k^2)=m>1\implies m|p$.
 A: This is not enough. A counterexample is $p=9$. We must have $2\leq k < 3$, so $k=2$. For $k=2$ we have $k^2=4$ and $p-k^2=5$ and $\gcd(4,5)=1$. 
However, when the last inequality is changed form a strict one into a non-strict one, it is true. 
So we should have for all integers $2\leq k \color{red}{\leq} \sqrt p$ that $\gcd(k^2,p-k^2)=1$.
 Suppose that $p$ is not prime, then it has a divisior $l$ smaller than or equal to $\sqrt{p}$. 
Then $l|l^2$ and $l\mid p-l^2$. Hence $\gcd(k^2,p-k^2)\geq l>1$. Contradiction. So $p$ is prime. 
A: Since $\ (k^2,p-k^2) = (k^2,p) = 1\iff (k,p) = 1,\,$ your criterion is equivalent to testing that $\,p\,$ is coprime to all $\,k\le \sqrt p,\ $ i.e. it is equivalent to the brute-force trial divisor factorization / primality algorithm that tests all integers below the square root of $\,p\,$ as possible factors.
Note that we need $\,k\le \sqrt p\ $ not $\, k < \sqrt p\ $ in order to find the prime factor $\,q\,$ of $\,q^2$.
A: This is almost correct.
If $p$ is not prime, say $p=k\cdot m$ with $2\le k\le m$, then $2\le k\le\sqrt p$ and $k\mid \gcd(k^2,p-k^2)$.
Hence by contraposition: 

If $p>1$ and $\gcd(k^2,p-k^2)=1$ for all $k$ with $2\le k\le\sqrt p$, then $p$ is prime.

