I just solved the same issue by going to the "App Store" on my watch and downloading a single app. This prompted me for my password, which I entered, and now apps are installing just fine from within my "Watch" app on my iPhone.