Word – MS Word Section Numbering (e.g. A.1.1) includes Chapter (A.1) but not Changing with Chapter Number

I found my own answer: The trick is to have the new style "based" on an existing style that's already part of the numbering scheme.

For example, if I want to have two styles at the "Heading 2" level, one named Heading 2 and one named Heading 2 Red but both at the same level in terms of numbering, I would do the following:

1. Follow the instructions linked above to set the multilevel numbering, and set it for Heading 1, Heading 2, Heading 3, etc. Leave Heading 2 Red alone, at this point.
2. Edit the style for Heading 2 Red and set the "Style based on" to Heading 2. This will have it inherit the same numbering settings (and other settings) as Heading 2.

You can do this for any other styles that you want to have at the same level in your numbering scheme, e.g. a Heading 3 Red style at the Heading 3 level or another Heading 2 Green style at the Heading 2 level.

As annoying as it is, the official answer seems to be "you can't":

The "heading" category in the Cross-reference dialog box only includes the built-in headings. What you can do is manually bookmark your appendix paragraphs as required and then insert a cross-reference to the bookmark.
https://answers.microsoft.com/en-us/msoffice/forum/msoffice_word-mso_winother-mso_2016/have-new-heading-styles-appear-in-cross/6735eaff-5212-4bec-8865-30208ec4f64f

As you mentioned, Word is willing to use numbered items as well, so that's probably your best bet without custom bookmarks or diving into macros.