Mark Liberman's post at Language Log 'On the origins of 'American Indian hyphens' (with updates) locates "the practice of writing American Indian words -- especially proper names -- with multiple internal hyphens" in the 19th century. The earliest usage Mark has found so far is in an 1823 publication about an 1819-20 expedition across the USA.
Here in Australia, by about 1791 hyphens between syllables were common when the Sydney Language was being written down by the English colonists (who had arrived in 1788).
A good example is David Collins' list near the end of his 1798 An account of the English colony in New South Wales (pp.407-413 in 1975 edition; at "What follows is offered only as a specimen, not as a perfect vocabulary of their language").
NAMES CHIEFLY OF OBJECTS OF SENSE NEW SOUTH WALES ENGLISH Co-ing The sun Yen-na-dah The moon Bir-rong A star Mo-loo-mo-long The Pleiades War-re-wull The Milky Way Ca-ra-go-ro A cloud [etc]
Collins regularly uses intersyllabic hyphens also in his 'A short vocabulary of the New Zealand language' (sc. Māori) in the same volume. The practice might be more common where vernacular words are used in English running text, such as:
That they have ideas of a distinction between good and bad is evident from their having terms in their language significant of these qualities. Thus, the sting-ray was (wee-re) bad; it was a fish of which they never ate. The patta-go-rang or kangaroo was (bood-yer-re) good, and they ate it whenever they were fortunate enough to kill one of these animals. (Collins Appendix I)
Note that the Sydney Language words they were recording are generally monomorphemic and I think it is safe to say that the writers realised this by the time they made up their lists. John Hunter's vocabulary, partly copied from Collins, uses intersyllabic hyphens in only some of the words, and in others seems to use a hyphen to separate morphemes (1793, An historical journal of the transactions at Port Jackson and Norfolk Island, Chapter 15). A third possible pattern in Collin's practice is that a hyphen precedes a syllable with secondary stress.
Another First Fleeter, Watkin Tench, uses hyphens when focussing on the syllables, such as in
June, 1791. On the second instant, the name of the settlement, at the head of the harbour, Rose Hill, was changed, by order of the governor, to that of Par-ra-màt-ta, the native name of it. (Watkin Tench 1793 A complete account of the settlement at Port Jackson, Chapter 15)
Tench has an interesting phonetics remark, in which he uses a hyphen to separate units which would help an English reader better approximate the target phonetics:
Not only their combinations, but some of their simple sounds, were difficult of pronunciation to mouths purely English. Diphthongs often occur. One of the most common is that of a e, or perhaps, a i, pronounced not unlike those letters in the French verb haïr, to hate. The letter y frequently follows d in the same syllable. Thus the word which signifies a woman is Dyin; although the structure of our language requires us to spell it Dee-in. Watkin Tench 1793 A complete account of the settlement at Port Jackson, Chapter 17 *
I infer that Tench means here (by "the structure of our language") that English orthography would suggest the wrong pronunciation were the word written Dyin, namely as a disyllable like dying, and he can avoid that by writing Dee-in. Perhaps Tench also wanted to represent a disyllable, or bimoraic syllable: Dawes wrote this word as "Deeyin 'Woman or wife'". Note that this Sydney Language word was borrowed into NSW English as gin, assimilated as a monosyllable with short vowel (rather than, say, jean with long vowel).
The first vocabularies recorded in Australia were Cook's and Banks' lists taken down at Endeavour River in 1770. Those did not use hyphens. They are similarly absent from the 1777 vocabulary recorded for Cook by his surgeon Mr Anderson at Adventure Bay (Tasmania), at least as published in 1821.
So, we are hardly any closer to understanding "the origins and spread of this orthographic practice", but it seems to have arisen in the late 18th century and continued through the 19th century.
* Note: I quote from the 1961 Angus & Robertson edition Sydney's first four years "With an introduction and annotations by L.F. Fitzhardinge". The online version of Tench drops the intersyllable hyphens (and simplifies in other ways); it might be truer to the 1793 edition which I haven't checked, but for now I trust Fitzhardinge.