Ubuntu – Bluetooth won’t find devices!

This is not really the answer required, relating to using blueman, but gives an alternative to blueman, as a solution to the more general problem that blueman didn't solve: "I would like to have a "connect" option in the tray icon for the paired devices."

That is provided by the 1.2.9 version of blueberry, the Linux Mint configuration tool for bluetooth, available in Linux Mint 19.2. I have tested it in the Xfce version (New features in Linux Mint 19.2 Xfce, under XApps improvements: "The Blueberry systray menu now lets you connect or disconnect paired devices with a click of the mouse". The same is said for the Mate and Cinnamon versions).

Right-clicking the tray icon shows the menu:

I am not sure if/when blueberry 1.2.9 is/will be available in the very Ubuntu repos, and for the moment I can only find as deb to download the version 1.2.5, but this PPA provides the 1.2.9 version.

sudo add-apt-repository ppa:trebelnik-stefina/cinnamon
sudo apt update
sudo apt install blueberry 

Another solution would be a panel launcher to connect, for example by running this script, which will connect the first unconnected bluetooth headset that it finds.

After saving the script and making it executable, create a .desktop file in ~/.local/share/applications to run that script:

[Desktop Entry]
Version=1.0
Type=Application
Name=Bluetooth-connect
Comment=
Exec=sh -c '/path/to/script'
Icon=preferences-system-bluetooth-inactive
Path=
Terminal=false
StartupNotify=false

Then, add 'Bluetooth-connect' as a launcher to the Xfce panel. (That .desktop file can be used differently in other desktops of course. It can also be found by search & launch tools like Synapse, WhiskerMenu, etc.)