Cannot connect to any Bluetooth headphones or speaker

I can see the Available Devices in Settings -> Bluetooth, but I cannot connect to any: headphones, speakers or Xiaomi Mi Band just do not work with my Samsung Galaxy S4 mini (GT-I9192).

Any suggestions?

Did you try to remove device-s and pair again ?