Let $n$ denote the size of the matrices $A,B$. Note that the Jordan normal form of a size-$n$ matrix $M$ can be completely recovered if one knows the rank of $(M - t I)^k$ for all eigenvalues $t$ of $M$ and $k = 1,2,\dots,n$ (via the "Weyr Characteristic"). In our case, $A + \lambda B$ has $0$ as its lone eigenvalue, so it suffices to consider the rank of $(A + \lambda B)^k$.
For $k = 1,\dots,n$, let $r_k = \max_{\lambda \in \bar{\Bbb F_3}} \operatorname{rank}(A + \lambda B)^k$. We note that the set $\{M : \operatorname{rank}(M^k) < r_k\}$ is a solution set to a system of polynomials. In particular, it is the set of matrices for which all $r_k \times r_k$ minors are zero.
This is enough for us to deduce that for each $k$, we have $\operatorname{rank}(A + \lambda B)^k = r_k$ for cofinitely many $\lambda$. In particular, the common zero set to a system of polynomials is the same as the zero-set of the product of these polynomials, and a zero-set of a polynomial of one variable must either be the entirety of $\Bbb {\bar F}$ or a finite subset.
Thus, $(A - \lambda B)$ must have constant Jordan form (corresponding to the maximal ranks $r_k$) for cofinitely many $\lambda \in \bar{\Bbb F_3}$.
Moreover, it is possible to obtain a bound on the number of solutions by considering the number and degrees of equations attained by setting the appropriate minors to $0$.
If we know that there are at most $m$ exceptions, then we also know that these exceptions are the zeros of a polynomial with degree at most $m$ and coefficients in $\Bbb F_q$, but this polynomial must split over $\Bbb F_{q^m}$. That is, a positive answer to your second question implies a positive answer to your third.
To be a bit more specific: we know that $A + \lambda B$ cubes to zero for all $\lambda$. With that, the only two equations that need to be accounted for are
$$
\operatorname{rank}(A + \lambda B) < r_1, \quad \operatorname{rank}(A + \lambda B)^2 < r_2.
$$
We have $\binom n r^2$ size-$r$ minors, and the entries of $(A + \lambda B)^2$ have at most degree $2$ with respect to $\lambda$. So, the first inequality gives us a system of $\binom n{r_1}$ degree-$r_1$ equations. Similarly, the second inequality gives us a system of $\binom n{r_2}$ degree-$2r_2$ equations. This is enough to deduce that the solution set in question is necessarily the zero set of some polynomial with degree
$$
m \leq 2\binom n{r_1}\binom n{r_2}r_1r_2.
$$
Note that if $\operatorname{rank}(A + \lambda B) = r_1$, $\operatorname{rank}(A + \lambda B)^2 = r_2$, and $(A + \lambda B)^3 = 0$, then we know that the Jordan form has $n-r_1$ blocks in total, with $r_1 - r_2$ blocks of size at least $2$ and $r_2$ blocks of size at least $3$. Because $(A + \lambda B)^3 = 0$, the Jordan form has no blocks of size $4$ or greater. All together, this gives us $n + r_2 - 2r_1$ blocks of size $1$, $r_1 - 2r_2$ blocks of size $2$, and $r_2$ blocks of size $3$.
If there are no blocks of size $2$, then we have $r_1 = 2r_2$, and $r_2$ blocks of size $3$.
We could get a better bound on the number of exceptions as follows. Because $B$ has no blocks of size $2$ we find that (up to similarity over $\Bbb F_q$) $B$ must have the form
$$
B = \pmatrix{0 & I_{k} & 0\\ 0 & 0 & I_{k}\\ 0 &0 &0\\ &&&0},
$$
with $k = \frac 12 \operatorname{rank}(B)$. Because $A$ and $B$ commute, $A$ must have the form
$$
A = \pmatrix{A_1 & A_2 & A_3 & A_{14}\\0 & A_1 & A_2 & 0\\ 0 & 0 & A_1 & 0\\ 0&0&A_{43}& A_{44}},
$$
So, that
$$
A + \lambda B = \pmatrix{A_1 & A_2 + \lambda I_{k} & A_3 & A_{14}\\ 0 & A_1 & A_2 + \lambda I_k & 0\\ 0 & 0 & A_1 & 0\\
0&0&A_{43}& A_{44}}.
$$
Now, note that the degree of a size $k$ minor for $A + \lambda B$ is at most equal to the minimum of the number of rows and the number of columns selected that correspond to either the $1,2$ or $2,3$ block.
Note that if $SA_1S^{-1}$ is in Jordan form, then we have
$$
\pmatrix{S \\ & S \\ && S\\ &&& I}(A + \lambda B) \pmatrix{S \\ & S \\ && S\\ & &&I}^{-1} = \\
\pmatrix{SA_1S^{-1} & SA_2S^{-1} + \lambda I_{k} & SA_3S^{-1}\\ 0 & SA_1S^{-1} & SA_2S^{-1} + \lambda I_k\\ 0 & 0 & SA_1S^{-1} \\ &&& A_{44}}.
$$
Similarly, we can also put $A_{44}$ into its Jordan form without losing any structure.
Best Answer
If $A$ is $n\times n$ and nilpotent, then its characteristic polynomial will be $t^n$ (or $(-1)^nt^n$, depending on how exactly you define the characteristic polynomial).
By the Cayley-Hamilton Theorem, evaluating the polynomial at $A$ will be zero; thus, if $A$ is nilpotent, then necessarily $A^n = 0$. Conversely, if $A^n=0$, then $A$ is nilpotent.
Thus, it suffices to check if $A^n=0$. You can do this in $\lceil\log_2(n)\rceil$ steps by repeated squaring.