Yes, except more flavorful peppers are used than cayenne in Mexico. Dried cayenne has heat but little flavor. Cocoa works well with chilies, green herbs with minty qualities, onion, garlic and the 'sweet' spices, especially cinnamon, allspice and ginger.
Lance-- Are you able to get dried thyme or marjoram? The sage is good. It would be good if you could get some 'sweet' spices like cinnamon, allspice, clove, nutmeg, cardamom, fennel--those sorts of things--as well as ground chilies of various qualities. Paprika isn't very good for much more than a bulking agent for low/slow cooks. I'm on the road for several weeks or I'd send some. I realize getting stuff is not a matter of hitting the corner store for you.
Anyway, based on what you have in your list, try:
1/2 c cocoa powder, preferably Dutch-processed, unsweetened*
3/4 c light brown sugar (or white if l.b. is unavailable)
3/4 c paprika
3 T sage
3 T garlic powder
4 T onion powder
2 T black pepper
1 t cayenne
* if all you have is sweetened, decrease the sugar by 1/4 c
If I see who ships to APOs perhaps I can send stuff sooner than when I get back home.
Should you be able to get cinnamon, allspice and ginger I'd look at 1 t of each. If you can only get one and not the others, increase to 1.5 t of that one but I wouldn't go higher.
I don't put salt in rubs as if you've read any of my stuff you know. I salt the meat first, allow the salt to draw miosture for several minutes, then apply the salt over the rub.