First part of answer:
...
if x = 1 then return composite
...
This is correct, because if $x=1$ then all other squaring operations $x := x^2 \pmod{n}$ in the loop leave $x=1$ and therefore
$$a^{2^r\cdot d} \not \equiv -1\pmod{n}$$
Second part: You get $s$ and $d$ from $n-1$ with a loop like this (the loop invariant is $n-1= 2^s d)$
d := n-1;
s := 0;
while even(d) do begin
d := d/2;
s := s+1;
end;
The claim is not true.
It is not true that if $H_n(x) \equiv 2x^n \pmod {x^r-1,n}$, then $n$ is either a prime number or Fermat pseudoprime to base $2$.
Proof :
Let us consider the case where $n$ is an even number greater than $2$.
So, $n$ is neither a prime number nor Fermat pseudoprime to base $2$.
Using the following expression
$$H_{2k}=(-1)^k2^k(2k-1)!!\left(1+\sum_{j=1}^{k}\frac{(-4k)(-4k+4)\cdots (-4k+4j-4)}{(2j)!}x^{2j}\right)$$
we have, using $(n-1)!!\cdot 2^{\frac n2}(\frac n2)!=n!$,
$$\begin{align}H_{n}&=(-1)^{\frac n2}2^{\frac n2}(n-1)!!\left(1+\sum_{j=1}^{\frac n2}\frac{(-2n)(-2n+4)\cdots (-2n+4j-4)}{(2j)!}x^{2j}\right)
\\\\&=(-1)^{\frac n2}2^{\frac n2}(n-1)!!\bigg(1+\frac{(-2n)(-2n+4)\cdots (-4)}{n!}x^{n}
\\&\qquad\qquad\qquad\qquad\qquad+\sum_{j=1}^{\frac n2-1}\frac{(-2n)(-2n+4)\cdots (-2n+4j-4)}{(2j)!}x^{2j}\bigg)
\\\\&=(-1)^{\frac n2}2^{\frac n2}(n-1)!!\bigg(1+\frac{(-4)^{\frac n2}(\frac n2)!}{n!}x^{n}+\sum_{j=1}^{\frac n2-1}\frac{(-4)^j(\frac n2)!}{(\frac{n-2j}{2})!(2j)!}x^{2j}\bigg)
\\\\&=2x^n+(2^n-2)x^n+\frac{(-1)^{\frac n2}n!}{(\frac n2)!}+n(-1)^{\frac n2}\sum_{j=1}^{\frac n2-1}\frac{(n-2j-1)!}{(\frac{n-2j}{2})!}\binom{n-1}{2j}(-4)^j
\end{align}$$
So, there is a polynomial $f$ with integer coefficients such that
$$H_n(x)=2x^n+(2^n-2)x^n+(x^r-1)\times 0+nf$$
Now, if $n$ is an even pseudoprime to base 2, then we get $2^n-2\equiv 0\pmod n$, so it follows that $H_n(x) \equiv 2x^n \pmod {x^r-1,n}$.
Therefore, $n=161038$ is a counterexample.$\qquad\blacksquare$
It is true that if $n$ is either a prime number or Fermat pseudoprime to base $2$, then $H_n(x) \equiv 2x^n \pmod {x^r-1,n}$.
Proof :
For $n=3$, we have
$$H_3(x)=2x^3+(x^r-1)\times 0+3(2x^3-4x)\equiv 0\pmod {x^r-1,3}$$
In the following, $n$ is an odd number greater than $3$.
Using the following expression
$$H_{2k+1}(x)=(-1)^k\cdot 2^{k+1}(2k+1)!!\bigg(x+\sum_{j=1}^{k}\frac{(-4k)(-4k+4)\cdots (-4k+4j-4)}{(2j+1)!}x^{2j+1}\bigg)$$
we have, using $n!!\cdot 2^{\frac{n-1}{2}}(\frac{n-1}{2})!=n!$,
$$\begin{align}H_{n}(x)&=(-1)^{\frac{n-1}{2}}\cdot 2^{\frac{n+1}{2}}n!!\bigg(x+\sum_{j=1}^{\frac{n-1}{2}}\frac{(-2n+2)(-2n+6)\cdots (-2n+4j-2)}{(2j+1)!}x^{2j+1}\bigg)
\\\\&=(-1)^{\frac{n-1}{2}}\cdot 2^{\frac{n+1}{2}}n!!\bigg(x+\frac{(-2n+2)(-2n+6)\cdots (-4)}{n!}x^{n}
\\&\qquad\qquad\qquad\qquad+\sum_{j=1}^{\frac{n-3}{2}}\frac{(-2n+2)(-2n+6)\cdots (-2n+4j-2)}{(2j+1)!}x^{2j+1}\bigg)
\\\\&=(-1)^{\frac{n-1}{2}}\cdot 2^{\frac{n+1}{2}}n!!\bigg(x+\frac{(-4)^{\frac{n-1}{2}}(\frac{n-1}{2})!}{n!}x^{n}
\\&\qquad\qquad\qquad\qquad\qquad+\sum_{j=1}^{\frac{n-3}{2}}\frac{(-4)^j(\frac{n-1}{2})!}{(2j+1)!(\frac{n-2j-1}{2})!}x^{2j+1}\bigg)
\\\\&=(-1)^{\frac{n-1}{2}}\cdot 2^{\frac{n+1}{2}}n!!x+2^nx^{n}
\\&\qquad\qquad\qquad\qquad+\sum_{j=1}^{\frac{n-3}{2}}\frac{n!\cdot(-1)^{\frac{n-1}{2}}\cdot 2^{\frac{n+1}{2}}(-4)^{j}}{(2j+1)!\left(\frac{n-2j-1}{2}\right)!\cdot 2^{\frac{n-1}{2}}}x^{2j+1}
\\\\&=(-1)^{\frac{n-1}{2}}\cdot 2^{\frac{n+1}{2}}n!!x+2^nx^{n}
\\&\qquad\qquad\qquad\qquad+n\sum_{j=1}^{\frac{n-3}{2}}\frac{(n-2j-2)!\binom{n-1}{2j+1}(-1)^{\frac{n-1}{2}}\cdot 2\cdot (-4)^{j}}{\left(\frac{n-2j-1}{2}\right)!}x^{2j+1}
\\\\&=2x^n+(2^n-2)x^{n}+2n(-1)^{\frac{n-1}{2}}\sum_{j=\color{red}{0}}^{\frac{n-3}{2}}\frac{(n-2j-2)!}{\left(\frac{n-2j-1}{2}\right)!}\binom{n-1}{2j+1}(-4)^{j}x^{2j+1}
\end{align}$$
So, there is a polynomial $g$ with integer coefficients such that
$$H_n(x)=2x^n+(2^n-2)x^n+(x^r-1)\times 0+ng$$
Since $n$ is either a prime number or Fermat pseudoprime to base $2$, we get $2^n-2\equiv 0\pmod n$.
It follows that $$H_n(x)\equiv 2x^n\pmod{x^r-1,n}\qquad\blacksquare$$
Best Answer
I think some version of the (deterministic) Miller-Rabin Test should do the trick. It is usually used as a probabilistic test for whopping big numbers, but it can be repurposed as a deterministic test for smaller fixed ranges.
The core of the Miller-Rabin test is the notion of a "probable prime" for some base $a$. Specifically, let $n$ be an odd prime, and write $n - 1 = d \times 2^s$ for some odd $d$. Then, it follows that $a^d \equiv 1 \pmod{n}$ or $a^{d 2^r} \equiv -1 \pmod{n}$ for some $0 \leq r < s$. (The wikipedia page has reasoning for this).
If $n$ is any number, and $a<n$, we could run the same test, and if that test passed we would call $n$ a strong pseudoprime for base $a$. The usual Miller-Rabin test is based on doing this for a lot of different (randomly chosen) $a$, and some number-theoretic argument saying that if $n$ is composite, the probability of not finding an $a$ demonstrating this is vanishingly small (after trying a lot of them).
However, if Wikipedia is to be believed (I haven't followed up the reference), then for $n < 2^{64}$ it is sufficient to test $a \in \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37\}$. Somehow there are no composite numbers below $2^{64}$ which are a strong pseudoprime for all these $a$.
The above test is very fast, and altogether prime testing would require at most $12 \times 64$ modular exponentiations (this will be well below 1ms). For smaller $n$, you could even use a smaller list of possible $a$'s.