How old is the Castilian phrase a la orden? Is it similar in meaning to the Mexican phrase "a sus órdenes"?
I can only give you a hint of how old is the expression. First of all, we need to know that an "orden" is a word used to denote confraternities or societies of men, starting from the crusaders in the XII century (catholic military orders) and following with the medieval knights in the XV century (chivalry orders or knighthood orders). So it is just normal that in the first Spanish dictionary issued between 1726 and 1739 by the Real Academia, the expression is already present:
A la orden, o A las órdenes. Término cortesano con que alguno se ofrece a la disposición de otro.
In this case, the term "cortesano" means:
Cortesano. Comedido, atento, urbano y cortés.
It does not say that the expression was only used within the orders, it was just used as a polite expression to denote that you were at other's service. So I would say that the expression began within a civil context, and ended up in the nowaday's military organizations.
It would be worth trying to discover when the word "orden" acquired its meaning as something that must be obeyed in Spanish. In the first Spanish dictionaries (from centuries XV and XVI), the word "orden" is just described as the position things have in a series, apart from the "Order" meaning. So maybe the expression originally could be something larger, like "he de servir a la Orden", "yo sirvo a la Orden X", "darse a la Orden" (to devote to the Order), "hacer merced a la Orden" (to be willing to do what the Order says), or something like that. Then the expression was shrunk to "a la orden" meaning "sirvo a la orden de vos". But this last bit is just me supposing.