I think that was the Cotswolds and Malverns Express and not the Cheltenham Spa Express; HSTs appeared on Cheltenham runs before 1984, instead I believe an extra off-peak run was added in that year to/from Cheltenham.
Both existed: both introduced in 1984 if I remember right.
The Cotswold and Malvern Express was the only through Cotswold line service during the daytime off-peak, which went to Great Malvern.
The Cheltenham Spa Express went to Cheltenham and again was the only through service off-peak. This was the extra off-peak run you mention, but it definitely carried the Cheltenham Spa Express name.
I'm not sure whether there were HSTs on either line before 1984, but I do remember a big thing being made of the introduction of these two daytime services.
I have station working books for Paddington from 1981 and 1985, from the BR Coaching Stock group on groups.io.
There appear to be no HSTs to Cheltenham in 1981, with two conventional hauled services in the evening peak at 1622 and 1727.
In 1982 (timetable on Timetable World) there was a 1743 to Cheltenham, fast to Didcot at 1816 - I'd imagine these timings meant it must have been an HST. So it looks like HSTs (well, one trip) to Cheltenham were introduced in 1982. No sign of any daytime trip of any description, though.
By 1985 the Cotswold and Malvern Express and Cheltenham Spa Express are both present, departing 1010 and 1040 respectively. The station working book mentions both names.
The evening peak HST is also still there at 1742, as well as a service operated by conventional hauled stock at 1625.