The word 'highly' in its present meaning is recorded in Old English as far back as 900 AD, so I wouldn't be surprised if the phrase itself is just as old.
The earliest recorded use of the word highly attached to the verb speak in this way is in Thomas Macaulay's 'Historyof England' published in 1849. Of course, as H says above, "to speak highly of" may have been used many times before that in speech.