Is "Solving two-variable quadratic polynomials over the Integers" is an NP-Complete Problem?
As you noted, solving that Diophantine equation is not complicated, mathematically.
All is needed is to find the necessary remainders $r$ of $x$ modulo $B$ such that $Ax^2-C$ is a multiple of $B$, then all integer solutions are of the form $x=Bn+r$ and $y=(C-Ax^2)/B=(C-A(Bn+r)^2)/B$.
One way to find the remainders $r$ is to

factor $B=\prod_i q_i^{a_i}$, where $q_i$ are different primes,
solve the congruences $Ax^2-C\equiv 0\pmod{q_i}$, which in the worst case have two solutions $\pm t_i$,
lift these solutions to solutions $\pm\theta_i$ of $Ax^2-C\equiv 0\pmod{q_i^{a_i}}$ and
glue these solutions, using the Chinese Remainder Theorem to get a solution of $Ax^2-C\equiv0\pmod{B}$. Note all the $\pm$ choices.

Factoring $B$ is possibly hard, but maybe it isn't. My outdated knowledge is that nobody knows. Also maybe it is also possible to find the remainders $r$ without factoring $B$. What the proof that I saw exploits to conclude that the problem is NP-complete is the decision that still remains to be made.
The original decision problem becomes checking if one of the choices of $\pm$ is such that the interval $x\geq0$, in other words $n\geq -r/B$, intersects (and intersection contains an integer) the interval where $n$ is such that $y\geq0$. Compared to the bit size of $(A,B,C)$ there can be many remainders $r$ to test. I will not quantify this claim. Let the proof of its NP-completeness give evidence of it.
In Moore and Mertens' The Nature of Computation, section 5.4.4 there is a reduction (with parts left as exercises) of the SUBSET SUM decision problem to this decision problem (let's call it QDE).

Let me sketch their argument just to get a taste of how the input to SUBSET SUM is encoded in the input to QDE and how the choices of $\pm$ correspond to the subsets that one can consider in SUBSET SUM. Maybe I or someone else can expand the details later.
SUBSET SUM gets a set (or maybe a multi-set) $X=\{x_1,x_2,\ldots x_n\}\subset\mathbb{N}$ and $t\in \mathbb{N}$ and asks if there is a subset $Y\subset X$ such that the sum of its elements is $t$. If one defines $S=2t-\sum_{k=1}^{n}x_k$ then SUBSET SUM is equivalent to the existence of $\sigma_i\in\{-1,1\}$ such that $$S=\sum_{k=1}^{n}\sigma_kx_k$$

Here we have already choices of subsets encoded as choices of $\pm$.

Taking $m$ such that $2^m&gt;\sum_{k=1}^{n}x_k$ this equation is equivalent to $$S\equiv \sum_{k=1}^{n}\sigma_kx_k\pmod{2^m}$$
If we choose $q_1,q_2,...,q_n$ relatively prime odd numbers (the first odd primes suffice), the Chinese Remainder theorem ensures that there are $\theta_1,\theta_2,\ldots,\theta_n$ such that
$$
\begin{align}
\theta_k&amp;\equiv x_k\pmod{2^m}\\\ 
\theta_i&amp;\equiv0\pmod{\prod_{k=1,k\neq i}^{n}q_k^m}\\\ 
\theta_k&amp;\not\equiv0\pmod{q_k}
\end{align}
$$

The $\theta_i$ will be, for the QDE problem to be created, the solutions $\theta_i$ that we mentioned at the beginning.

The first group of these congruences imply that SUBSET SUM is equivalent to $$S\equiv \sum_{k=1}^{n}\sigma_k\theta_k\pmod{2^m}\qquad\qquad(*)$$

Now they build the quadratic equation, which solubility is equivalent to the solubility of this congruence.

They define $H=\sum_{k=1}^n\theta_k$ and $K=\prod_{k=1}^{n}q_k^m$. Observe that any $x$ of the form $$x=\sum_{k=1}^{n}\sigma_k\theta_k$$ satisfies $$H^2-x^2\equiv0\pmod{K}$$
Then, through a pair of exercises, they argue why there are choices for picking $q_i$ and a $\lambda_1$ large enough such that $2H&lt;K$, and $|t|&lt;H$, and ensuring that $(*)$ has a solution if and only if the Quadratic Diophantine Equation
$$\underbrace{(\lambda_12^{m+1}+K)}_{A}x^2+\underbrace{2^{m+1}K}_{B}y-\underbrace{(\lambda_12^{m+1}H^2-KS^2)}_C=0$$
has a solution $x,y\geq0$.
Notice how this equation re-writes as
$$\lambda_12^{m+1}(H^2-x^2)-K(S^2-x^2)=2^{m+1}Ky,$$
The choices made in the technical details are such that when there is a solution $x,y\geq0$ for this equation it is always the case that $H^2-x^2$ is already known to be a multiple of $K$ and $S^2-x^2=(S+x)(S-x)$ a multiple of $2^{m+1}$.