The first time I submitted an app to Windows Store, it got failed by privacy settings. In the guide lines that were provided, it was stated that if any data about the user is saved or shared, a privacy statement was neded. We didn’t save or share any user data but we added a privacy statement in the app before submitting but it got failed anyway. We got a bit confused but found out that we also needed a link to the privacy statement in the store (see picture below), and that the reason that we needed the privacy statement was because we used the internet connection. The guide lines are now updated with this information, see 4.1.1 in Windows Store certification guide lines.
So before submitting your app, if you are using the internet connection or have that capability set in the app manifest, don’t forget to submit a privacy statement – both in the app and in the store as well!