After wasting time checking lots of unhelpful advice, I found a solution thanks to IonuČ›-Alexandru Popa at binaryfork_. Here's a summary:
Pair the device (if not already paired)
Go to Settings > Bluetooth and devices > View more devices
Scroll down to 'More devices and printer settings' (near the bottom of the window): (this is the crucial step that most of the unhelpful advice misses)
Right-click the device and choose 'Properties', then the 'Bluetooth' tab
Edit the name and click OK
Disconnect the device (or just shut off Bluetooth) then reconnect it/turn it back on (this is important to prevent the device name reverting to the default)
I found this about 30 replies down, and wanted to thank the wizard who found it, so I posted as a reply to the first posting - but it gets pushed to the bottom anyway.
This one did the trick!
Thanks!
The only thing I would add is
after renaming the device, click Apply (not OK)!
Other than that, I almost posted this very same wording myself!