There are 3 aspects to the scenario of successfully using Cortana with a Bluetooth Handsfree device (e.g. car).
First, is Cortana enabled on the phone. You will need to check Cortana availability in for your language/country to see whether it is supported. If not, then your phone will use the WP8.0 speech engine (with less functionality than Cortana). Note that this has nothing to do with Bluetooth.
Second, can your Handsfree device send a command to the phone to activate speech? Many cars do not support this. In WP8.1 Update 1 you will see a contact called "Cortana" or "Speech" on your car (if your car downloads contacts). Dialing that number provides an alternate way to activate speech.
Third, starting speech requires that a bidirectional audio connection be opened between the phone and car so that the phone can send speech prompts to your car's speaker, and receive your voice commands from the car's microphone. This works with most cars, but some cars can experience problems with this.