What are the security risks of Bluetooth and what technologies and best practices should be used to protect my device? What can an attacker do once a malicious device is paired with mine?

Specifically 


Is it a good idea to remove & re-pair my devices on a set interval (thinking that this is changing the Bluetooth PIN)
What is the security impact of making my device or computer "discoverable"?
What kind of access does a Bluetooth enabled device get on my system?
How can I control the scope of access a Bluetooth device has?  (if my phone were compromised I'd want to limit the exposure my PC has)
Are there Bluetooth security features that may (or may not be enabled)?  How can I audit for the presence (or lack of) these features?
Assuming encryption is a security feature that can be enabled, is it required or is it optional?  (moreover could an SSL Strip for Bluetooth be created?)


I'm interested in information that addresses mobile phones (iOS), OSX, Windows, and Linux operating systems

(Note: This answer is from 2013. A lot has changed in Bluetooth since then, especially the sharp rise in BLE popularity, new attacks, deprecated features. Having that said, most of it is still applicable.)
Introduction
I'll try to the best of my knowledge to approach your questions without touching the technical parts of the Bluetooth technology itself. I've learned a lot of the following while I had to write a security report to shape a BYOD policy. Knowing you, I won't have to lecture you on that there's nothing 100% secure, everything we do is just to make it harder for the bad guys.
What Bluetooth is NOT

Bluetooth itself as a technology isn't secure, it's not only about the implementation, there are some serious flaws in the design itself.

Bluetooth isn't a short range communication method - just because you're a bit far doesn't mean you're safe. Class I Bluetooth devices have a range up to 100 meters.

Bluetooth isn't a mature communicate method (security-wise). With smart phones, it has turned into something totally different from what it was meant to be. It was created as a way to connect phones to peripherals. My advice: Don't use Bluetooth for anything serious.


How is Bluetooth being secured now?

Frequency hopping like crazy: Bluetooth uses something called AFH (Adaptive Frequency Hopping). It basically uses 79 channels in the 2.4 Ghz ISM band and it keeps hopping between them on a rate of 1600 hops/s, while observing the environment and excluding any existing frequencies from the hopping list. This greatly reduces interference and jamming attempts.

E0 cipher suite: Uses a stream cipher with a 128-bit key.

Undiscoverability: Unless you set your device to "discoverable" it won't respond to scanning attempts and your 48-bit BD_ADDR (the address that identifies your Bluetooth-enabled device) won't be revealed.

Pairing: Unless the devices are paired with the parties' consent they won't be able to communicate. A pairing request can only be made if you know the other device's BD_ADDR (through scan or previous knowledge).



Is it a good idea to remove & re-pair my devices on a set interval
(thinking that this is changing the Bluetooth PIN)

Yes. It's a very good idea. You're eliminating the risks of being exploited by your trusted devices. Given that we usually pair devices for insignificant reasons (sending a file to an acquaintance, getting a VCard from a person you met somewhere..) it's very likely to build a huge list of "trusted" devices if you use Bluetooth a lot.

What is the security impact of making my device or computer
"discoverable"?

The problem with making your device discoverable is that you're advertising your BD_ADDR to anybody asking for it. The only way to pair with another device is by knowing the BD_ADDR. In a targeted attack, it's gonna take some time to brute-force the 48-bit BD_ADDR.
In the normal case, knowing your BD_ADDR shouldn't be a big problem, but in case there's a vulnerability in your phone or the Bluetooth software on your computer, it's better to be under the radar. Another problem is the impact on privacy; by being discoverable you're letting unpaired (untrusted) parties know when you're around.

What kind of access does a Bluetooth enabled device get on my system?

In the normal case (no vulnerability to allow arbitrary code execution) it all depends on the Bluetooth profiles supported by your device. Usually, you can assume that your computer supports all profiles. I'll just list a few:

BHIDP (Bluetooth Human Interface Device Profile) will give access to your mouse and keyboard event firing (moving the mouse and sending keyboard keys).
BIP (Basic Imaging Profile) will give access to your camera.
A2DP (Advanced Audio Distribution Profile) will give access to your MIC and to your audio output.
OBEX (OBject EXchange) is what you usually need to worry about. Depending on the implementation, it could give access to your files, phonebook, messages, etc.


Are there Bluetooth security features that may (or may not be
enabled)? How can I audit for the presence (or lack of) these
features?

Prior to Bluetooth V2.1, when implementing the protocol itself, the developer has the options to use Security Mode #1, which means no security at all. Devices are allowed to communicate without the need of pairing, and encryption isn't used.
Bluetooth V2.1 and newer require encryption.
As a user, there are a few things you can do to make your Bluetooth usage more secure. (See below)

Assuming encryption is a security feature that can be enabled, is it
required or is it optional?

As in the previous question, it's implementation-dependeant. Usually encryption is used by default in PC-PC, smartphone-smartphone, and PC-smartphone communication. As of Bluetooth V2.1, encryption is enabled by default.

What can an attacker do once a malicious device is paired with mine?

Basically, anything that your device supports. To demonstrate this, just use an application called Super Bluetooth Hack, you'll see very scary things including:

- Ringing: playing sounds of incoming call, alarm clock.
- Calls: dialing number, ending a call.
- Keys, Pressed keys: pressing and watching pressed keys
- Contacts
- Reading SMS
- Silent mode: turning on or off
- Phone functionality: turning off the network / phone
- Alarms
- Clock: change date and time
- Change network operator
- Java: start, delete java applications
- Calendar
- Memory status
- Keylock

So what's wrong with Bluetooth?

Complete trust in the paired device: A paired device has access to virtually all of the profiles supported by the other device. This includes OBEX and FTP (File Transfer Profile).

Profiles have too much freedom: Profiles are allowed to choose whatever security mode they want. You're even able to implement your own version of OBEX without Bluetooth requiring you to use encryption or authentication at all. (Prior to Bluetooth V2.1)

Weaknesses in E0: Since 1999, E0 vulnerabilities started to show. It was proven that it's possible to crack E0 with 264 rather than the 2128 previously believed. Year after year, researchers have discovered more vulnerabilities, leading to the 2005 attack by Lu, Meier and Vaudenay. The attack demonstrated the possibility to recover the key with 238 operations.

Pairing is loosely defined: Devices are allowed to implement their own pairing methods, including a 4-digit PIN which can be cracked in no time.


Finally, for good practice guidelines:
I'll list some of the important NSA Bluetooth Security Recommendations (I've modified some of them and added some of my own):

Enable Bluetooth functionality only when necessary.
Enable Bluetooth discovery only when necessary.
Keep paired devices close together and monitor what's happening on the devices.
Pair devices using a secure long passkey.
Never enter passkeys or PINs when unexpectedly prompted to do so.
Regularly update and patch Bluetooth-enabled devices.
Remove paired devices immediately after use.

Update: An hour ago I was diving in the Bluetooth V4.0 specs, and, to my surprise, it appears they're still using E0 for encryption, and there were no good changes to the pairing mechanism. What's even worse is that they're pushing forward the number-comparison pairing mechanism, in which the users are shown a six-digit number on the two devices and asked to verify if they're the same. Which, in my opinion, opens huge doors for social engineering attacks.

For pairing scenarios that require user interaction, eavesdropper protection makes a simple six-digit passkey stronger than a 16-digit alphanumeric character random PIN code.

Source
Update 2: It seems like this "Just Works" 6-digit PIN is indeed problematic. Mike Ryan has demonstrated an attack on BLE and released the code as his tool "crackle" to brute-force the temporary key and decrypt the traffic.
