Hmmm.
I wasn't able to do it just now either, er - until I could.
Not sure I can walk you through how I did it, but here goes -
I have a Note 3 on 4.4, sorry, but I think this still applies.
I had a lost BT earpiece and a Moto G paired, via the Connections - Bluetooth screen. So each had a gear wheel setting.
No way to select and delete, for sure.
So I unpaired each, and yes, both still there without a gear wheel setting.
I exited, looked at the Bluetooth app (cleared a little cache but irrelevant), then reopened the Bluetooth settings.
I pressed / held my device (Note 3 name) probably more than once. It switches between being visible to all, and not.
So I guess with both of mine unpaired, they disappeared with a press / hold initiating a new scan.
Didn't take any before shots, just an after.
Hope it works for you. There probably is a shorter sequence to achieve the same, it's just the way my brain works.