I'm experiencing the same problem. From my experience and what I've read elsewhere, the watch somehow launches Pandora when it reconnects to the phone via Bluetooth. I can replicate this by simply putting the watch into airplane mode then reenabling Bluetooth. Without fail, Pandora starts playing. This occurs even if Pandora was force quit or if the phone had been restarted (that is, Pandora is not just waiting in the background for someone to push play).
Oddly, the Pandora app isn't even "open" when I double-click the home button after a random start. Swiping up shows a song is playing, but double-clicking the home button and swiping through open background apps doesn't show Pandora. If I launch Pandora after it starts playing on its own, it shows the song currently playing.
I thought it might be the Pandora app for Pebble, but deleting that made no difference. In fact, I'm reluctant to blame Pandora at all. At 12:30 am today, the phone randomly started playing back a Zello two-way radio message I hadn't previously acknowledged from the previous afternoon.
After awakening to Pandora in the middle of the night several times, I started putting the watch into airplane mode at night and that stopped the random music. I forgot to do that last night and got the Zello wake up call. I'll try deleting Pandora on my phone, but the Zello incident I suspect that it'll just launch something else.