Well, it turns out, that my code was correct after all. Apparently the Bluetooth Stack had entered a faulty state that could only be recovered by switching the device off and then turning it on again.
FYI: I have Nexus 7 devices. One of the first edition (I think it came out at the end of 2012) and a recent one.
Bluetooth Low Energy does not work on the 2012 Nexus 7. (Not even after switching it off and on again).
Both devices are running Android 4.4.2.
I conclude, that Bluetooth Low Energy does not work on Nexus 7 2012 and is unstable on the current Nexus 7.
How very sad this is.