
Not many travel lodges in this neck of the woods!!! I know the Mansfield hotel in Hawick allows dogs and is about 20 miles from Kelso.
Clovenfords will be a similar distance and there are some lovely walks nearby. There are a few hotels in Kelso itself but they could be expensive and not sure which take dogs but a web search would tell you. Some names are Roxburghe, Ednam House,and Cross Keys.