Paired with unknown device Galaxy S3

I noticed that my Bluetooth is turned on (I never use it and keep it off) and my phone is paired with an unknown device called "Deborah's iPhone".

My "Messages" application duplicated itself on the home screen.

Must I assume that my data was stolen?

How can I be asked to pair when my bluetooth is turned off in the first place?
No. The application on the home screen is just a shortcut and must have been created by mistake. You can unpair by clicking on the options button next to the iPhone's name. Also, iPhones don't support Bluetooth transfer with android so you needn't worry!