TRAVEL
I have found a text that uses "travell" to mean "work", dating from 1576.
In the introduction to "The Rocke of Regard" by George Whetstone, he uses the following passage:
and further, for that I know the most part of youth (to whome I chiefly dedicate the fruite of my travell) are so carelesse of their commoditie, as they set light of sound advice, unless such persuasions be sauced (in some respect) with their owne desires...And yet, least they lighting on some discourse of worth, shoulde by and by be led away with the sight of some wanton devise, I have published my travell under these foure following titles.
At some point between 1579 and 1587 (these dates being the period when Sir Thomas Bromley was Lord Chancellor), "travel" is used for "journey", in the Journals of the House of Lords (see 2nd snippet view).
Sir Thomas Bromley, Knight, Lord Chancellor of England, is at this Time so visited with Sickness, that he is not able to travel to the Upper House of this Our present Parliament, holden at Westm., nor there to supply the Room and Place in the said Upper House, among the Lords Spiritual and Temporal there assembled, as to the Office of the Lord Chancellor, or Lord Keeper of the Great Seal of England, hath been accustomed
TRAVAIL
If 1560 is early enough, one book alone contains several uses of "travail" meaning "work", and at least one where it means "make a journey".
The Calendar of State Papers, Foreign Series, of the Reign of Elizabeth, 1559-1560 contains this passage, dated Feb 12 1560, in which "travail" appears to cross the border from "work" to "journey":
As for his keeping watch, he thinks the French in Leith and Inchkeith would not deny but that the fleet had kept them waking. There has been never night since he came hither, being possible for men to travail upon the water, but that he has had 300 or 400 men armed in boats to guard the haven's mouth, that no succours should come in to them between the shore and the ships; and that they might not be able to put more men or victuals into Inchkieth.
A further example, from Feb 19, 1560, blurs the lines a little between the two meanings:
Cecil considered that Sir James Croftes was the meetest for that purpose, from his experience amongst the Scots, and his travail taken in the discourse of the said journey;
There are several (over 30) other uses of "travail" to mean "work" in the same publication, an example of which is below, from Feb 25, 1560:
Most heartily thanks him for his earnest travail about the said payment, and is right glad that it is so well ended.
Hence, it can be seen that travail was certainly used in the mid-late 16th Century to mean both work and journey, and that the same was also the case for "travel" a decade or two later.
Also, the hardship and difficulty of making any lengthy journey seems to be pertinent to the evolution from one meaning to the other.