I currently have this problem in Mint 19.3 (kernel 5.4.0-48-generic) on an X1 Carbon ThinkPad. My rfkill showed Bluetooth as Hard blocked. No idea why the following is necessary, but it worked for me:
sudo rfkill unblock bluetooth
I’ve had to do it twice in the last two weeks, which suggests something random is happening that results in Bluetooth being blocked after a restart. Random issues are always a hoot.