Yes I was able to install app from Watch AppStore. However the same app installed from Watch AppStore does not fully sync with the app. The whole process is buggy. Let me give you another example step by step:
App name: WeChat.
A) installing from Watch app on iPone failed as described in my original post.
B) Installing from App Store on Watch succeeded...
1. Open WeChat on Watch - I got the following message on Watch:
2. After restart iPhone, The WeChat app appeared on the "installed" list on Watch app (on iPhone)
3. Followed the above instruction to tap WeChat on the list, there is only one option for WeChat: Show app on Watch.
4. Toggled it off, viola: The WeChat app disappeared from Watch! And it won't toggle back on.
5. WeChat also disappeared from the "installed app" list on Watch app (on iPhone). It is now moved back to the previous "ready to install" apps list. and WON'T install.
By now, we have gone a full circle and back to where I started.
Reinstall WeChat on App Store on Watch, I am back to the first step above.
However some apps did work, e.g. Starbucks by installing directly from Watch's App Store.
