I was aware of the requirement for a privacy policy for the Windows Store (requirement 4.1.1), but when publishing my application it was rejected on the grounds that I absolutely had to provide this policy because I was using the Internet connection. So even if you do not collect information from your users, simply being connected requires this policy. It is unfortunate that Visual Studio validation does not detect this issue and that it is detected later during submission.
The privacy policy must be available in the application’s “Settings charm” as well as a link in the Windows Store. I based it on what Jim did in his applications (See below for a small correction) to add a link in my application to my own web page, if you do not have a website you could use Azure for free.
Correction for Jim’s code
There is a small error on his page, but not in his sample project attached to his blog. At point #5, the code should read:
// Add the main call to the privacy policy
SettingsPane.GetForCurrentView().CommandsRequested += DisplayPrivacyPolicy;