You may want to have a look into Hwang's Lemma which is known as a discrete (sufficient) analogy to Stein's Lemma though it is NOT a characterization. Generally speaking you can yield such a characterization when the undelying probability distribution is restricted to full rank regular exponential family because in that case you are actually characterizing the linear structure of the probability density.
[Hwang]Let $g(x)$ be a function with bounded expectation
$-\infty<Eg(X)<\infty$under the probability distribution $X~\varphi$
and $-\infty<g(-1)<\infty$ Then
(a)If $X~Poisson(\lambda)$ then $E(\lambda g(X))=E(Xg(X-1))$
(b)If $X~NegBinom(r,p)$ then $E([1-p] g(X))=E(\frac{X}{r+X-1}g(X-1))$
More generally I do not think there will be a characterization in a simpler form than [Eichelsbacher&Reinert] of $X \sim Q \Leftrightarrow E[(\mathcal{A}f)(X)]=0$ as you asked for. Here is my reasoning, since in discrete probability distributions the joint density of sample function usually contains order statistics as sufficient statistics. The related empirical process will based on the order statistics[Daly et.al]. If we write the stochastic empirical process in characterization(that is what Stein did) of some differential equation like $E[(\mathcal{A}f)(X)]=0$ then it must include such a sufficient statistics. Moreover if you read [Eichelsbacher&Reinert] carefully you can see they argue that in general a Gibbs measure must contain necessary many terms to describe the sample functions.
References
[Hwang]Hwang, Jiunn Tzon. "Improving upon standard estimators in discrete exponential families with applications to Poisson and negative binomial cases." The Annals of Statistics (1982): 857-867.
[Eichelsbacher&Reinert]Eichelsbacher, P., and G. Reinert. "Stein’s method for spatial Gibbs measures." Preprint (2003).
[Daly et.al]Daly, Fraser, Claude Lefèvre, and Sergey Utev. "Stein's method and stochastic orderings." Advances in Applied Probability (2012): 343-372.