With HSERIN/HSEROUT you can change the data-rate by writing directly to SPBRG.
Code:
Here:
    SPBRG = 129 ' 9600 @20MHz
    HSEROUT ["TEST AT 9600",13,10]
    PAUSE 10
    SPBRG = 64 ' 19200 @20MHz
    PAUSE 5000 ' Time to switch terminal program from 9600 to 19200
    HSEROUT ["TEST AT 19200",13,10]
    PAUSE 5000
    GOTO Here
You can't change DEFINEs at run time, so just write to SPBRG directly if you want to change data-rates with HSEROUT/HSERIN.

With DEBUG/DEBUGIN the data-rate & pins used are fixed, you can't change data-rates on the fly, and you'll want your osc frequency as close as possible to whatever you have it DEFINEed as.