I don't plan to go deeply into this question, but I do want to note that instances of "your highness[e]" occur at least as early as 1494 in search results from the Early English Books Online database. Two such instances occur in Anno XIIII. et XV. Henrici VIII.: The Kynge our soueraygne lorde Henrye the viij. after the conquest, by the grace of God king of England and of Fraunce and lorde of Irelande, at his parlyamente holden at London, the xv. day of April in the xiiii. yeare of his moste noble reygne: and from thence adiourned to Westminster the last day of Iuly the xv. yeare of his sayde reigne, and there holden to the honour of Almightye God and of holye Churche, and for the wealthe and profytte of thys hys realme, by the assent of the lords spiritual and temporall, [and] the commons in thys presente parliament assembled, [and] by aucthoritye of the same, hath, doo, to be ordeined, made, [and] enacted, certaine statutes and ordynaunces in maner and fourme folowing, [1575), as follows.
From "An Acte Concerning the High Wayes in the Wilde of Kent. Ca. xi":
In consideracion wherof, in maye please your highnesse of your blessed disposicion with the assente of the lordes spiritual and temporall, and the commons in this presente parliamente assembled and by the auctoritye of the same to enacte ordayne that it shalbe lefull to your sayde besecher his heires and assignes, owners of the sayde maner of Hempstede, at his and their propre costes & charges at any time on this side ye .xxvii. day of May which shallbe in the yere of our lord god .M.D.xxvii. by the ouersighte and assent of two Iustices of peace of the said county of Kente and .xii other discrete men, inhabitauntes within the sayde hundredes of, Cranbroke & Roluiden, to assigne, limitte and laye ouer and thoughe the landes of the sayde manour one other way, for cariages & passages of your grace and of your people and your and their heires and successoures, of as great largenesse in bredeth or larger than the sayd olde waye now being is, and as cōmodious for the sayd cariages and passages, as the same waye now being is or better extending and leading dyrectly betwene the sayde bridge and crosse, so that your grace and your people by the sayd new way so to be assigned and layed out, shall haue the more easye cariage, and passage, than is or of late tyme hath bene by the sayd olde waye.
This act treats the terms of the prospective highway improvement as subject to financing prior to May 27, 1527, dating the act to some time before that.
And from "An Acte Concerning the Six Clerkes of the Chauntery to Be Married. Cap. viii":
¶And for as muche as the sayde custome taketh no place nor vsage, but onely in the office of the sayde sixe clerkes but that it is permitted and suffered for maintenance of the sayd courte, that as wel the said coursetoures as the other clerkes aforesaid, may and doe take wiues and mary at their lybertye after the lawes of holy churche, and of longe tyme haue so done, without interruption or left of any person: It may therefore please your highness of your most aboundant grace, with the assent of the lordes spirituall and temporall and the commons in this present parlyamente assembled, and by auctoritye of the same, in consideration of the premisses, and also for that the sayd custome is not groūded vpon any law, to ordeine enacte, and establishe, that Iohn Treuerthen, Rycharde Welles, Oliuer •…der, Iohan Croke, Wyllyam Iessen, and Iohn Lemsey, nowe beynge in the office of the sixe clerkes of the Chauncery, & euery of them, and all other whiche in time to come shalbe in the same office, & euery of them, may and do take wiues & mary at their liberty, after the laws of holy churche.
Even earlier are these two instances from a 1494 translation of Bocaccio, Here begynnethe the boke calledde Iohn bochas descriuinge the falle of princis princessis [and] other nobles tra[n]slated i[n]to englissh by Iohn ludgate mo[n]ke of the monastery of seint edmu[n]des Bury...:
Ye may me saue and spyll with a worde / Make moost glad and moost dolerous / I nat requyre of you my souereyn lorde / But that ye wolde be to me gracious / For blode and kyn and my faders hous / All lefte behynde if ye list aduerte / And vndepartyd yeue to you myn herte
Which to your highnesse ought inough suffise / All thynge consideryd in your riall astate / Conceyued also howe in vncouth wyse / For your loue I stonde desolate / Saue of your mercy full disconsolate / Here is al and sum your loue I bye so sore / But ye do grace I can say you no more
...
Noble princes your reason do applie / Which ouer the people haue dominacōn / So prudently to gouerne theym and guye / ••at loue and drede by true affeccion / Preserue their hertis from fals rebellyon / ••th to your highnesse no thinge may more preuayle / Than true subieccion expert in poraile
And from Richard Arnold, In this booke is conteyned the names of ye baylifs custos mairs and sherefs of the cite of londo[n] from the tyme of king richard the furst ... (1503):
Therfore as euer poure subgems may bee. And crye youre grace hertely mercy. Neuer while they lyue as nye as god wyll put in their mynde to do eny thyng that in ther conceytes may redounde to the displesur of your highnesse In consideraciō that they haue ben your trewe lyegemen as they dare be reported by ther neybours being your trewe •ege people & at this daye bethe and entende to bee to their vttermest power to their lyues ende. Hit plesyth your highnes to bee so gracious an so merciable lorde vnto theym to pardon theym ther offence aforesayde So ignorantly done and semply. And doo dismisse thē out of the duresse whiche they be in And to assigne theym to bee at their libarte lyke as your other subgett{is} bee.
...
That it may therfore Please your highnesse of your most noble grace. & honorable lordshippis the premisses tenderly consydered to calle the sayd Iohn̄ W. befor you in examinacion vpon the premisses. and ther vpon o. deynue cōmaunde and directe that youre besecher maye in this behalue. a• deuly recompensed and restored for the loue of god. and in ye waye of charite and your besecher. shal dayly prey for the conseruacion of your highnes and of your ful noble lordshippis.
Altogether, Early English Books Online reports more than 13,000 matches in more than 2,000 different publications for "your highness" (in various spellings) from the period 1475 to 1700—and more than 56,000 matches in more than 4,200 different publications for "your majesty" (in various spellings) during the same period.
It thus appears that the form "your highness," "your majesty," "your lordship," etc., was probably already firmly in place in English by the dawn of printed books in England (circa 1475).