What makes a theory "Quantum"?
As far as I know, the commutator relations make a theory quantum. If all observables commute, the theory is classical. If some observables have non-zero commutators (no matter if they are proportional to $\hbar$ or not), the theory is quantum.
Intuitively, what makes a theory quantum is the fact that observations affect the state of the system. In some sense, this is encoded in the commutator relations: The order of the measurements affects their outcome, the first measurement affects the result of the second one.
I think this is a subtle question and I think it depends somewhat on how you choose to represent quantum mechanics. To see one extreme of this, consider the viewpoint put forth by Kibble in [1]. For simplicity I will be thinking of finite-dimensional quantum systems here; there are some subtleties in infinite dimensions but as far as I know the basic picture still holds. In this, he shows that if we describe the theory in terms of physical states (rays in the Hilbert space), then the dynamics of Schrödinger evolution correspond exactly to Hamiltonian evolution via the symplectic form from the Kähler structure on the projective Hilbert space (which is to say, the evolution is that of a classical system). However there are two distinctions which make quantum mechanics different from classical mechanics:
- The phase space must be a projective Hilbert space (as opposed to just a symplectic manifold), and the Hamiltonian is restricted to being a quadratic form in the homogeneous coordinates on projective space. In classical mechanics any (sufficiently smooth) function is admissible as a Hamiltonian.
- Composite systems are described differently. In classical mechanics the phase space of a composite system is the Cartesian product of the phase spaces. In quantum mechanics, it is the Segre embedding (which descends from the tensor product of Hilbert spaces). This is parametrically different; if the phase spaces of the two subsystems are $2m$ and $2n$, then in classical mechanics the composite system has dimension $2m+2n$, whereas in quantum mechanics it has dimension $2(n+1)(m+1)-2$. The extra states are the entangled states. Virtually all the observable consequences of QM come here, e.g. Bell inequalities. Of course if we consider identical particles things get even a bit more complicated.
If you ignore the second point, and focus only on a single quantum system, the surprising conclusion is that every quantum mechanical system is a special case of classical mechanics (with the provision that again I haven't checked the details in infinite dimensions but it is at least morally true). However, part of the structure of quantum mechanics is how it describes composite systems so you can't just ignore this second point. A mathematician would say that this gives an injective functor from the category of quantum mechanical theories to the category of classical theories which is not compatible with the symmetric monoidal structures on the two.
I want to point out that this is emphatically not how we typically think of the correspondence principle in quantum mechanics. That is, it is a mapping from a finite-dimensional quantum mechanical system to a finite-dimensional classical system (of the same dimension). Normally, if we think about e.g. a free particle in one dimension, the Hilbert space for that quantum system is infinite dimensional, yet it corresponds to a 2-dimensional classical phase space. But the point is that, at least in this question, we can't restrict to the ordinary notion of correspondence since we don't have a physical interpretation for the system of equations describing the theory.
Additionally, despite the above example, whether a theory is classical or quantum has essentially nothing to do with where the states live. Indeed, if we just want to consider a free particle in one dimension again, we would typically describe its state as a self-adjoint trace class unit trace operator $\hat \rho$ on the Hilbert space $L^2(\mathbb R)$. In contrast, in classical mechanics we would describe a state as a probability distribution $\rho$ on the phase space $\mathbb R^2$ (note that in the above example we had only pure classical states i.e. only those described by a $\delta$ function on the phase space whereas now we have mixed states). However we could just as easily describe the quantum state by its Wigner function, in which case it lives in exactly the same affine space as the classical distribution. However the Wigner function satisfies slightly different inequalities than the classical probability distribution; in particular it can be slightly negative and cannot be too positive. The details of this were first worked out in [2]. In this case, it is the dynamics that give away the quantum nature. Specifically, to go from classical to quantum mechanics, we must replace the Poisson bracket by the Moyal bracket (which has $O(\hbar^2)$ corrections), indicating the failure of Liouville's theorem in the phase space formulation of quantum mechanics: (quasi)probability density is not conserved along trajectories of the system.
All of this is to say that it seems difficult (and maybe impossible) to try to find a single distinguishing feature between classical and quantum mechanics without considering composite systems, so if that is what you want, I'm not sure I have an answer. If you do allow for composite systems though, it is a pretty unambiguous distinction. Given this, it is perhaps not surprising that all the experimental tests we have which demonstrate that the world is quantum and not classical are based on entanglement.
References:
[1]: Kibble, T. W. B. "Geometrization of quantum mechanics". Comm. Math. Phys. 65 (1979), no. 2, 189--201.
[2]: H.J. Groenewold (1946), "On the Principles of elementary quantum mechanics", Physica 12, pp. 405-460.
Frame challenge: I think the question is based on a misleading premise.
While there are a number of characteristics typical of quantum theories as opposed to classical theories - some you've already listed in the question, and others have been suggested in the existing answers - there's no particular reason to expect there to be a single unambiguous rule that categorizes any arbitrary theory as either quantum or classical.
Nor is there any particular need for such a rule. You give the example of quantum gravity. However, the reason we want a quantum theory of gravity is not because it has the tag "quantum" attached to it, as if it were a handbag that would not be adequately fashionable without the correct label, but because we want it to be able to answer certain questions about reality which we already know General Relativity can't answer.
In short, don't worry about whether the theory is "quantum" or not - worry about whether it answers the questions you want answered or not.
Also relevant.
Addendum: the same goes for the existing theories, of course. We don't like the Standard Model because it is quantum. We like it because it works.