Is there any efficient algorithm for primality testing for numbers that are of the form $4k+3$ using the square root function?
Let me start with a counterexample where your algorithm gives the wrong answer: i.e., where $N$ is composite but your algorithm concludes it is prime.  Suppose $N=91$ and $a=9$.  Then $a^{(N-1)/2} = 9^{45} \equiv 1 \pmod{91}$, so $a$ passes your check to be a QR.  Also, $a^{(N+1)/4} = 9^{23} \equiv 81 \pmod{91}$ and $81^2 \equiv 9 \pmod{91}$, so this passes your second test, your algorithm will conclude that 91 is prime.  However, 91 is not prime: $91=7 \times 13$.  Thus your algorithm has drawn the wrong conclusion in this case.  This demonstrates that your algorithm can output incorrect answers in at least some cases.



Actually, there is a more serious problem with your algorithm.  There is no number $N$ where your algorithm will ever output "composite".  It thinks that all numbers are primes.  More precisely, for every $N$, your algorithm will either loop forever (trying to find a number that passes the QR test, in vain), or will terminate and output "prime".  So, your algorithm is about as wrong as could be.

You can see this by applying some number theory.  You have a test whether $a$ is a QR and a second test based on the square root insight.  If $a$ passes the first test, it will pass the second one. 

Here's why.  Your QR test succeeds if $a^{(N-1)/2} \equiv 1 \pmod N$.  Your second test succeeds if $(a^{(N+1)/4})^2 \equiv a \pmod N$.   The latter is equivalent to $a^{(N+1)/2} \equiv a \pmod N$.  But $a^{(N+1)/2} \equiv a \times a^{(N-1)/2} \pmod N$.  Therefore, if $a^{(N-1)/2} \equiv 1 \pmod N$, then (multiplying both sides by $a$) we immediately see that we must have $a^{(N+1)/2} \equiv a \pmod N$.

Each of the $k$ passes of your algorithm basically amounts to looking for an $a$ that passes the first test, and then checking whether it passes the second test -- but based on the prior insight, we see that any $a$ that passes the first test will be guaranteed to pass the second test as well.  Thus, if the algorithm ever finds any value $a$ that passes the QR test, the second test will automatically pass and the algorithm will output "prime".

The lesson to learn: any time you think you have an algorithm that looks promising, it's worthwhile to code it up and try it on some test cases and see if it seems to work well.  Trying it on a few test cases is not a substitute for a proof of correctness, but it can be a helpful way to weed out some incorrect algorithm quickly.



Finally, on to your real question: can we use something like this to build a primality test? Well, you can think of the Miller-Rabin primality test as loosely based on something like this.  They are based on a characterization of what the square roots of $1$ should look like, if $N$ is prime.  If you encounter a square root of $1$ that is not $1$ or $-1$, you can conclude that $N$ is not prime.  However, it's not limited to numbers $N$ of the form $N=4k+3$, so in that sense it is definitely different.