I wonder why the insistence on the (English) word rule, especially as German wikipedia translates / redirects it to interpretation. Isn’t it enough for your purposes to see it stated, named and credited as Born’s Deutung (Jordan 1927, p. 811), assumption (Dirac 1927, p. 257), Interpretation (Hilbert et al. 1928, p. 29), or Auffassung (Schrödinger 1927, p. 967; Handbuch der Physik 1928, p. 589)?
Added:
To your edit asking “who first linked Born’s name to an explicit statement about measuring arbitrary observables” (though nothing prevents a hamiltonian from being “arbitrary”...): if not von Neumann (1932, footnotes 8, 118, 122), then I’d guess E. Bauer (1933, p. 42; translation 1962, p. 39) who writes, for a superposition $\psi=\smash{\sum_k\beta_k\psi_k}$ of eigenstates belonging to eigenvalues $\alpha_k$ of a “physical quantity” $A$,
Nous admettrons qu’une expérience faite sur un système à l’état $\psi$ peut nous donner l’une quelconque de ces valeurs $\alpha_k$ avec une probabilité égale à $\overline\beta{}_k\beta{}_k$.
Ce dernier postulat entrevu par Einstein, énoncé en toute précision par Born et développé par Dirac est comme la clef de voûte de l’édifice quantique.
(The mention of Einstein is also in Born (1926, p. 804; 1978, p. 232), Heisenberg (1927, p. 176), Pais (1982, pp. 1196-1197).) Bauer may have the first occurrence of “Born’s rule”, too, in Théorie quantique de la valence. Les liaisons homéopolaires. Bull. Soc. Chim. France. Mém. (5) 1 (1934) 293-347, p. 302:
Multiplions d'autre part $|\psi|^2$ par le volume $4\pi r^2dr$ compris entre les sphères de rayons $r$ et $r + dr$, nous obtenons, d’après la règle de Born, la probabilité de rencontrer l’électron dans la couche sphérique ainsi délimitée, c’est-à-dire à une distance du noyau comprise entre $r$ et $r + dr$.
Finally and perhaps most influentially, I would say that Born’s book Atomic Physics (1935) has everything you asked for (and essentially insisted he never wrote...):
§V.6. The Statistical Interpretation of Wave Mechanics.
We have already mentioned the interpretation of the wave function given by the author (p. 83). Let the proper function corresponding to any state be $\psi_E$; then $\smash{|\psi_E|{}^2dv}$ is the probability that the electron (regarded as a corpuscle) is in the volume element $dv$. (...)
Appendix XXII. The Formalism of Quantum Mechanics, and the Uncertainty Relation. (...)
The statistical interpretation of quantum mechanics consists in the following assumptions: To each physical quantity or “observable” belongs a real operator $A$. The proper functions $\psi_1$, $\psi_2$, ... correspond to the quantised states, for which the operator takes the value $a_1$ or $a_2$ or $a_3$ ... ; any function $\phi$ is a state, which is composed of these states (...) The coefficients $c_n$ of the expansion determine the strength with which the quantum state $n$ occurs in the general state $\phi$. The probability of then finding the proper value $a_n$ in a measurement is given by
$\smash{w_n=|c_n|^2}$.
In fact, Born already wrote the same things, slightly less polished, in proceedings of the Fall 1927 conferences in Como (translation p. 15; reprint p. 16) and Brussels (pp. 166–170). There he credits himself (1926, 1927) as well as Dirac (1927), Jordan (1927, 1927) and von Neumann (1927, 1928). This is likely where Bauer got his information.