Bluetooth can’t find any device

I don't think this is your problem, but it might be and doesn't seem to have been raised elsewhere. I bought a new MacBook Pro running Lion a few months ago, and found that the (also new) Magic Mouse would not connect automatically—I had to force it to connect after any disconnection from switching off the MM or from rebooting the MacBook.

One of the genii at the Genius Bar, after ½ hour of experimenting and in the process of telling me that Lion would have to be reloaded, suddenly realized that the MM connected upon being clicked. He stated that he had not run into this before and that it must be a new feature in Lion related to battery preservation.

Bottom line, try a single mouse click to initiate the Bluetooth connection.

I've had the same things happen over the past 6 months (mine's a mid-2012, thought). I've tried to find out the root cause on many occassions - but I'm pretty sure it's a culmination of many, many different factors (wear and tear, bumps/drops, formatting drives repeatedly, etc.). Just found this though:

§ UHE Button Operation: Your Bluetooth USB adapter may have UHE button, this is applied in the condition when computer system is without BTW driver installed but need to make connection with Bluetooth enabled keyboard or mouse or any HID devices

I also use iTerm2, which is notorious for provisioning issues (can't have a worse problem when it comes to the command line).

Bluetooth gets in the way a lot (for me), so I've messed with the settings quite a bit. I wouldn't be surprised if the same was true for you. Likely through iTerm as well, which worsened the situation.

The largest cause seems to be from inconsistent settings, firmware upgrades, and the kernel issues that come with them. Doesn't take long for it to start taking a toll on the battery, power settings, and worsening kernel panics, kind of like this (old but relevant): https://forums.gentoo.org/viewtopic-t-506162.html

You will have to dig deep. But the issue is buried under some random setting, plugin, or other microscopic detail. Find the source, then patch the kernel appropriately.