Thanks for the honourable mention, but I do think you're out of luck here …
\A\d will find the first number in your story (i.e., one without a dollar sign before it) but GREP cannot discern frames. That is, \A (and \Z) will not match the first (or last) character per frame (much like GREP cannot 'see' the individual lines per paragraph).
You are also correct in your observation that anchored objects make things even more complicated — I've seen anchors move around and disappear when I tried to manipulate the text around them with GREP.
I think it's safest to remove all dollar signs using the regular Find-and-Change (GREP sometimes has problems with \$, and you don't need a specialized GREP search to remove them either) and then just manually page through your document and insert them by hand where needed …