Connect to gatt server not working on Samsung Galaxy Core Prime (Android 5.1.1)

I have BLE app which works on devices with Android 6.0 and higher but I have issues on Samsung Galaxy Core Prime (Android 5.1.1). After call connectGatt nothing happens and callback receives only disconnected state.

I have cut out appropriate code

BluetoothManager bluetoothManager = (BluetoothManager) getSystemService(Context.BLUETOOTH_SERVICE);
BluetoothAdapter bluetoothAdapter = bluetoothManager.getAdapter();
final BluetoothDevice device = bluetoothAdapter.getRemoteDevice(address);
Log.e("BluetoothLeService", "connect: connectGatt(this, false, mGattCallback)");
BluetoothGatt bluetoothGatt = device.connectGatt(this, false, mGattCallback);

private final BluetoothGattCallback mGattCallback = new BluetoothGattCallback() {
    @Override
    public void onConnectionStateChange(BluetoothGatt gatt, int status, int newState) {
        if (newState == BluetoothProfile.STATE_CONNECTED) {
            Log.e("BluetoothLeService", "onConnectionStateChange: STATE_CONNECTED");
        } else if (newState == BluetoothProfile.STATE_DISCONNECTED) {
            Log.e("BluetoothLeService", "onConnectionStateChange: STATE_DISCONNECTED");
        }
    }

    @Override
    public void onServicesDiscovered(BluetoothGatt gatt, int status) {
    }

    @Override
    public void onCharacteristicWrite(BluetoothGatt gatt, BluetoothGattCharacteristic characteristic, int status) {
    }

    @Override
    public void onCharacteristicRead(BluetoothGatt gatt, BluetoothGattCharacteristic characteristic, int status) {
    }

    @Override
    public void onCharacteristicChanged(BluetoothGatt gatt, BluetoothGattCharacteristic characteristic) {
    }

    @Override
    public void onMtuChanged (BluetoothGatt gatt, int mtu, int status) {
    }
};

And here is log

E/BluetoothLeService: connect: connectGatt(this, false, mGattCallback)
I/StatusBar: Icon Only
D/BluetoothGatt: connect() - device: CC:4B:73:22:9D:DB, auto: false
D/BluetoothGatt: registerApp()
D/BluetoothGatt: registerApp() - UUID=7d428718-b549-4021-8a45-9d3bd2afd462
D/BtGatt.GattService: registerClient() - UUID=7d428718-b549-4021-8a45-9d3bd2afd462
D/SamsungIME: Dismiss ExpandCandiate
D/PanelView: There is/are notification(s) 
D/CustomFrequencyManagerService: releaseDVFSLockLocked : Getting Lock type frm List : DVFS_MIN_LIMIT  frequency : 1248000  uid : 1000  pid : 2975  tag : ACTIVITY_RESUME_BOOSTER@4
I/Timeline: Timeline: Activity_windows_visible id: ActivityRecord{2bfa99a5 u0 com.streamunlimited.streamsdkdemo/.ui.setup.SetupDeviceActivity t43} time:3838458
W/ActivityManager: mDVFSHelper.release()
D/CustomFrequencyManagerService: acquireDVFSLockLocked : type : DVFS_MIN_LIMIT  frequency : 1248000  uid : 1000  pid : 2975  pkgName : ACTIVITY_RESUME_BOOSTER@8
D/BtGatt.GattService: onClientRegistered() - UUID=7d428718-b549-4021-8a45-9d3bd2afd462, clientIf=6
D/BluetoothLeService: Trying to create a new connection.
D/BluetoothGatt: onClientRegistered() - status=0 clientIf=6
D/BtGatt.GattService: clientConnect() - address=CC:4B:73:22:9D:DB, isDirect=true set own addr = false own addr type:0
D/BtGatt.btif: btif_get_device_type: Device [cc:4b:73:22:9d:db] type 3, addr. type 0
D/IOP_DB_BT: db_query_create: id EnforceMasterRole :: key KEY_BDADDR, value cc:4b:73:22:9d:db
D/IOP_DB_BT: db_query_add_key: key KEY_LMP_MFCT, value 15
D/IOP_DB_BT: db_query_add_key: key KEY_LMP_VER, value 9:24838
D/IOP_DB_BT: db_query_add_key: key KEY_DIR_ALL, value 1
D/IOP_DB_BT: db_query_execute: result 1
D/bluedroid-mrvl: bt_vnd_mrvl_if_op(L95): opcode = 7
I/SurfaceFlinger: id=153 Removed TetupScanAc (3/9)
I/SurfaceFlinger: id=153 Removed TetupScanAc (-2/9)
I/Timeline: Timeline: Activity_idle id: android.os.BinderProxy@21558ec5 time:3838516
W/SurfaceFlinger: couldn't log to binary event log: overflow.
D/CustomFrequencyManagerService: releaseDVFSLockLocked : Getting Lock type frm List : DVFS_MIN_LIMIT  frequency : 1248000  uid : 1000  pid : 2975  tag : ACTIVITY_RESUME_BOOSTER@8
D/BatteryService: !@BatteryListener : batteryPropertiesChanged!
W/bt-btif: bta_gattc_conn_cback() - cif=4 connected=0 conn_id=4 reason=0x0004
W/bt-btif: bta_gattc_conn_cback() - cif=5 connected=0 conn_id=5 reason=0x0004
W/bt-btif: bta_gattc_conn_cback() - cif=6 connected=0 conn_id=6 reason=0x0004
D/BtGatt.GattService: onConnected() - clientIf=6, connId=0, address=CC:4B:73:22:9D:DB
D/BluetoothGatt: onClientConnectionState() - status=133 clientIf=6 device=CC:4B:73:22:9D:DB
E/BluetoothLeService: onConnectionStateChange: STATE_DISCONNECTED

Lines that looks suspicious are

W/bt-btif: bta_gattc_conn_cback() - cif=4 connected=0 conn_id=4 reason=0x0004
W/bt-btif: bta_gattc_conn_cback() - cif=5 connected=0 conn_id=5 reason=0x0004
W/bt-btif: bta_gattc_conn_cback() - cif=6 connected=0 conn_id=6 reason=0x0004

I found that reason 4 means

PAGE TIMEOUT (0x04)
The Page Timeout error code indicates that a page timed out because of the
Page Timeout configuration parameter. This error code may occur only with the
Remote_Name_Request and Create_Connection commands.

in documentation https://www.bluetooth.org/DocMan/handlers/DownloadDoc.ashx?doc_id=421043&_ga=2.243934277.1321770839.1542020684-854809025.1539785109

Also line

D/BluetoothGatt: onClientConnectionState() - status=133 clientIf=6 device=CC:4B:73:22:9D:DB

which is just makro for GATT_ERROR based on https://android.googlesource.com/platform/external/bluetooth/bluedroid/+/android-4.4.4_r2.0.1/stack/include/gatt_api.h

I have also tried nRF Connect app and it fails to connect too with: Error 133 (0x85):GATT ERROR

Do you know any possible reason for this and solution too? Thanks

from Connect to gatt server not working on Samsung Galaxy Core Prime (Android 5.1.1)