L'introduction du mot orange pour le fruit semble beaucoup plus ancienne d'après TLFi (même référence). Safran se trouve un peu plus tôt; vers le 12e siècle, et safran est jaune orangé plutôt qu'orange.
Le cuivre vient à l'esprit comme une matière dont la couleur peut se rapprocher de l'orange, et le métal est connu depuis l'Antiquité (ce qui ne dit rien sur l'utilisation du mot cuivre comme nom de couleur).
Fauve, ocre, cinabre sont des mots liés à des nuances d'orange et il faudrait vérifier leur usage ancien.
Une autre piste serait les noms utilisés pour les couleurs en héraldique avant le 16e siècle. Malheureusement, je n'ai trouvé que des références héraldiques "récentes", utilisant déjà le mot orangé - en fait, cela est révélateur, comme le montrera la suite (le Moyen-Âge n'aime pas la couleur orange).
Pour ce qui est du Latin, que je consulte dans la recherche d'un mot en Vieux Français, je copie d'un autre forum:
... le problème se pose de la délimitation entre le rouge et le jaune: celle-ci n'est pas forcément nette.
- Croceus désigne le jaune en renvoyant au safran : dans l'élégie à Mécène (Appendice Virgilien) : il est associé à roseus, purpureus, comme épithète de l'Aurore, ce qui le rapproche de l'orangé.
- Flammeus: c'est la couleur du feu : orange, certes, mais qui peut tendre aussi sur le jaune.
- Luteus renvoie à la sarrette, plante utilisée en teinturerie pour donner une sorte de jaune : chez Ovide, Métamorphoses (15. 351), il désigne le soufre jaune pâle, mais chez Lucain (2.361), il est associé à flammeus!
Il est à noter que les premiers orangers arrivent en Europe seulement au XIVe siècle, bien que les Espagnols connaissent cet arbre par l'intermédiaire des Arabes à partir du XIe siècle.
Un autre passage intéressant, qui indiquerait que "l'orange" tel que nous le connaissons n'existait peut-être pas au Moyen-Age:
Au Moyen-Age, les mélanges étant considérés comme impurs (influence du christianisme…), la couleur orange n'était pas obtenue à partir du jaune et du rouge, mais grâce au safran, puis au "bois brésil", une essence provenant des Indes et de Ceylan - qui donna son nom au Brésil. Rappelons-nous qu'à cette époque, les femmes rousses étaient souvent accusées de sorcellerie, au point de finir sur le bûcher…
Finalement, ce document semble être la bonne référence. Je n'en reproduis ici que la toute première phrase:
Traiter de la couleur orange au Moyen-Âge revient quasiment à évoquer
une couleur qui n’existe pas, du moins pas telle que nous l’entendons
aujourd’hui : positionnée au sein d’un spectre chromatique, dégageant une
gamme de nuances, étalonnée sur un nuancier.
En résumé, au Moyen-Âge seuls les couleurs pures sont valorisées, et l'orange est un mélange de rouge et de jaune, deux couleurs chargées négativement sur le plan culturel à l'époque. Par contre, il est proche de l'or, ce qui est positif. Il faut noter aussi que cette couleur était alors difficile à produire sur le plan technique. Donc il n'y avait vraisemblablement pas de mot en usage courant pour la couleur orange avant la fin du Moyen-Âge.