gnome-bluetooth not working properly

Solution found, not sure why that works.

sudo apt-get install pulseaudio-module-bluetooth

reboot your system.

sudo systemctl start bluetooth.service

now open the gui utility for the bluetooth and make sure bluetooth is set on "on"

in the terminal type

bluetoothctl

make sure that the command

show

actually shows something similiar to

Name: debiansystem
Alias: debiansystem
Class: 0x0c010c
Powered: yes
Discoverable: yes
Pairable: yes
...

now trust, pair and then connect to your device.

This worked, at least for me