Now I can connect successfully from Windows 8! I achieved that installing Toshiba Bluetooth Stack from http://aps2.toshiba-tro.de/bluetooth/?page=download-toshiba (I read something about that somewhere on Internet).
But the problem is still present with my Android phone.