Try holding down the button on your bluetooth device when hitting the scan button on your phone. I had to do this to get it to show up in the list. Hope that helps
Wow, I searched a long time to find this method except I have a cheapo (but decent) JABRA bluetooth headset. It has a single button and yes you must hold down the button while beginning to scan. The S5 found my device. Thank you so much!