Cats’ Strand (Ruthwell), Catstrand (Dumfries) and Cat Strand (Kells) all look to be transparently formed from CAT and STRAND ‘a little stream or run of water, a rivulet’. This is how the Place-Names of the Galloway Glens interprets Cat Strand (Kells)  and is behind the rather more elaborate explanation the Ordnance Survey Name Book gives for Catstrand (Dumfries):
“This name applies to where a small stream crossed the road at the top end of [the] Kirkgate. The name [originates] from the fact of the place [having been] formerly haunted by witches [in] the shape of cats.” 
Another possibility is offered by John Mactaggart’s Scottish Gallovidian Encyclopedia. He defines CATSTRAN’ as ‘a very small stream’.  This is the DSL‘s only citation for this word and, other than these places-names, I’ve not seen it anywhere else. 
It’s hard to know if the names above are CAT + STRAND or CATSTRAN’. CAT appears in plenty of local place-names, including Cat Syke (Gretna, Westerkirk) which is the eastern D&G equivalent of Cat Strand. And there are several ‘animal’ + STRAND place-names in Galloway: Otter Strand (Minnigaff), Goat Strand (Carsephairn, Girthon, Borgue), Hare Strand (Carsephairn), Heron Strand (Carsephairn), Ged Strand (Balmaclellan). The size of the stream might offer a way in, but with only 3 examples so far, there’s not much to go on. Perhaps more will come to light in estate maps and field-name surveys.
Update 18/08/2021: I spotted another CATSTRAN’ while reading ‘The Gold Wells of Cairnsmore’ in Lowran Castle by Robert Trotter. It’s used in Mactaggart’s sense of ‘a very small stream’. It also antedates the Mactaggart example by two years. No a muckle antedating – but it’s ma first yin an A’m fair pleased wi it!
Here’s the extract where it appears:
“From its [Cairnsmore] summit also, rushes many a torrent stream, wherein the hunter’s moon casts her clear light, as the fleet roe of the wood drinks the golden water from the sparkling stream. There Dr Dodds placed his water mills, anointed with an oil, the name of which was never yet known to the most cunning artisan, ‘north of the Tweed.’ They, in form and size, resembled those made of rushes by the school-boy, and placed in the cat-stran’ by the village school; and so powerfully attractive was this oil, that every morning before the sun rose above the horizon, he carried them home, their spokes thickly plated with the pure gold from the dashing stream.”
 Kirkcudbrightshire place-name 1830: ‘Cat Strand’. 2021. In Place-names of Kirkcudbrightshire. Glasgow: University of Glasgow. Retrieved 28 June 2021, from https://kcb-placenames.glasgow.ac.uk/place-names/?p=record&id=1830
 Mactaggart, John (1824) The Scottish Gallovidian Encyclopedia, or, The Original, Antiquated, and Natural Curiosities of the South of Scotland…, p. 128
 Robert Trotter (1822) Lowran Castle or the Wild Boar of Curridoo: with other tales illustrative of the superstitions, manners, and customs of Galloway, Dumfries: J. Swan, pp. 94-95