We have
$$ \# \{x\in \mathbb{F}_{q^{2n}}|\mathrm{Tr}_{\mathbb{F}_{q^{2n}}/\mathbb{F}_{q^2}}(x)=0 \hbox{ and } x=y^n \textrm{ for some }y\in \mathbb{F}_{q^{2n}}\} = \frac{\#\{y\in \mathbb{F}_{q^{2n}}|\mathrm{Tr}_{\mathbb{F}_{q^{2n}}/\mathbb{F}_{q^2}}(y^n)=0 \} +n-1}{ n}$$
since $\mathbb F_{q^n}$ contains all the $n$th roots of unity, so it suffices to calculate.
\begin{align*}
\# \{y\in \mathbb{F}_{q^{2n}}|\mathrm{Tr}_{\mathbb{F}_{q^{2n}}/\mathbb{F}_{q^2}}(y^n)=0 \} &= \frac{1}{q^2} \sum_{\lambda \in \mathbb F_{q^2} } \sum_{ y \in \mathbb F_{q^{2n}} }\psi_2 (\lambda \mathrm{Tr}_{\mathbb{F}_{q^{2n}}/\mathbb{F}_{q^2}}(y^n) ) \\ &= \frac{1}{q^2} \sum_{\lambda \in \mathbb F_{q^2} } \sum_{ y \in \mathbb F_{q^{2n}} }\psi_{2n} (\lambda y^n) ) \\& = q^{2n-2} + \frac{1}{q^2} \sum_{\lambda \in \mathbb F_{q^2}^\times } \sum_{ y \in \mathbb F_{q^{2n}} }\psi_{2n} (\lambda y^n) ) \\ &=q^{2n-2} + \frac{1}{q^2} \sum_{\lambda \in \mathbb F_{q^2}^\times } \sum_{ x \in \mathbb F_{q^{2n}} } \sum_{\substack{ \chi \colon \mathbb F_{q^{2n}}^\times \to \mathbb C^\times \\ \chi^n=1 } } \psi_{2n} (\lambda x) \chi(x) \\ &=q^{2n-2} + \frac{1}{q^2} \sum_{\lambda \in \mathbb F_{q^2}^\times } \sum_{ x \in \mathbb F_{q^{2n}} } \sum_{\substack{ \chi \colon \mathbb F_{q^{2n}}^\times \to \mathbb C^\times \\ \chi^n=1 } } \psi_{2n} (x) \chi(\lambda^{-1} x) \end{align*}
where $\psi_2 \colon \mathbb F_{q^2} \to \mathbb C^\times$ is a nondegenerate additive character and $\psi_{2n} = \psi_2 \circ \mathrm{Tr}_{\mathbb{F}_{q^{2n}}/\mathbb{F}_{q^2}}$
Now since $\chi$ has order $n$ and the quotient group $\mathbb F_{q^{2n}}^\times / \mathbb F_{q^2}^\times $ has order $q^{2n-2} + q^{2n-4} + \dots + 1$ which is divisible by $n$, $\chi$ must factor through this quotient group so $\chi(\lambda^{-1})=1$, giving
$$\#\{y\in \mathbb{F}_{q^{2n}}|\mathrm{Tr}_{\mathbb{F}_{q^{2n}}/\mathbb{F}_{q^2}}(y^n)=0 \} = q^{2n-2} + \frac{q^2-1}{q^2} \sum_{\substack{ \chi \colon \mathbb F_{q^{2n}}^\times \to \mathbb C^\times \\ \chi^n=1 } } \sum_{ x \in \mathbb F_{q^{2n}} } \psi_{2n} (x) \chi( x) .$$
Here the inner sum $\sum_{ x \in \mathbb F_{q^{2n}} } \psi_{2n} (x) \chi( x)$ vanishes for $\chi$ trivial and is a Gauss sum of absolute value exactly $q^{n}$ for $\chi$ trivial. This gives an estimate with main term and error term
$$ \left| \#\{y\in \mathbb{F}_{q^{2n}}|\mathrm{Tr}_{\mathbb{F}_{q^{2n}}/\mathbb{F}_{q^2}}(y^n)=0 \} -q^{2n-2} \right| \leq (n-1) (q^2-1) q^{n-2} $$
I can show that exceptions occur at most for $n=3$. (Primality of $n$ is never used.)
Since $n$ is odd, $\mathbb F_{q^{2n}} = \mathbb F_{q^2} \otimes_{\mathbb F_q} \mathbb F_{q^n}$. The trace map $\operatorname{Tr}:\mathbb F_{q^{2n}} \to \mathbb F_{q^2}$ is obtained by tensoring the identity map $\mathbb F_{q^2} \to \mathbb F_{q^2}$ with the trace map $\operatorname{tr} : \mathbb F_{q^n} \to \mathbb F_q$.
Thus, choosing an arbitrary basis of $\mathbb F_{q^2}$, we can write any $a$ as a pair of elements $a_1,a_2 \in \mathbb F_{q^n}$, and your condition that $y \in \mathbb F_{q^n}$ satisfies $\operatorname{Tr}(y)\neq 0$ but $\operatorname{Tr}(ay)=0$ is equivalent to the condition that $\operatorname{tr} (y) \neq 0$ but $\operatorname{tr} (a_1 y ) =\operatorname{tr}(a_2 y)=0$. (We can ignore the condition that $y\neq 0$ as it is implied by the condition that $y$ has trace zero.)
Since the trace map of a product is a perfect $\mathbb F_q$-linear pairing on $\mathbb F_q^n$, such a $y$ exists unless $1$ is an $\mathbb F_q$-linear combination of $a_1$ and $a_2$.
I will show there must exist a member of $\mathcal A$ that has this unusual property by bounding the number of members of $\mathcal A$ that do have this unusual property.
Note that every member of $\mathcal A$ is in the subgroup of order $q^n+1$, thus has norm to $\mathbb F_{q^n}$ equal to $1$. This is a nonsingular quadratic equation in $a_1,a_2$. For each $\lambda_1,\lambda_2$ in $\mathbb F_q$, not both zero, $\lambda_1 a_1 + \lambda_2 a_2 =1$ is a linear equation. There can be at most two solutions to a linear equation together with an nonsingular quadratic equation in two variables, since it gives a nontrivial quadratic equation in one variable.
Summing over possible choices of $\lambda_1,\lambda_2$, the number of members of $\mathcal A $ with this unusual property is at most $2 (q^2-1)$. So we can only have all members of $\mathcal A$ with this property if
$$ \frac{q^n+1}{q+1} \geq 2 (q^2-1)$$
i.e.
$$q^n+1 \geq 2 (q^2-1) (q+1).$$
For $n\geq 5$, the left side dominates the right side for any $q$.
Best Answer
Generically the intersection of the surfaces described by these two equations is an algebraic curve of genus $4$. Once one has made sure that this curve is absolutely irreducible, by Weil there are $\mathbb F_q$-points provided that $q$ is big enough. Weil assumes a smooth curve, so it can be a pain to handle singularities. However, there are explicit bounds, like Theorem 5.4.1 in the third edition of Fried and Jarden's Field Arithmetic: If the absolutely irreducible affine curve has degree $d$, then the number of $\mathbb F_q$-points is at least $q+1-(d-1)(d-2)\sqrt{q}-d$. In your case $d=6$. This lower bound is positive once $q\ge419$. So one has to check the smaller cases directly, or has to resort to Joe Silverman's suggestion from the comments.