Hello Erel.
Problem cause found:
Testing with Nordic Connect app, it said: "Location service is disabled" ...
As you confirmed, we need to declare ACCESS_COARSE_LOCATION permission because Google requires it.
OK. it was on the manifest, but it is mandatory to activate Location to use Bluetooth???
On this phone yes, it is confirmed.
Phone brand: Wiko
Android version: 6.0
Android security patch level: October 5, 2016
Thanks in avance for your comments.