If you try to add the WNS (Windows Notification Service - aka Push Notifications) to your Windows Phone 8.1 application, you may encouter the same problem as I did recently.
Microsoft provides nice tutorial, however they do not tell you everything. First pain comes in the block of code labeled Step 2. These two lines of code seem quite nice until you run the code. The call of CreatePushNotificationChannelForApplicationAsync() will probably result in "The application does not have the cloud notification capability." error (HRESULT value 0x803E0110). Now this is where Microsoft's tutorial (as well as Google) leaves you with no help. Neither the PushNotificationChannel class nor CreatePushNotificationChannelForApplicationAsync function documentation mentions what to do.
Perhaps the first thing that will come to your mind is setting this capability in the application manifest (WMAppManifest.xml). But whoops - there is no such capability listed! The only one close to this is ID_CAP_PUSH_NOTIFICATION. Yeah, but the scenario (and result) is exactly the same.
So, after some time, being quite desperate I tried to search Google for the error code (0x803E0110). Bah, just 5 links - and all look similar, being just lists of error codes. I tried this one which in fact turned to be a good one - it contains a list of HRESULTs with respective codes, messages and also defines. Here I learned that the one I am investigating is WPN_E_CLOUD_INCAPABLE - let's Google this. And voilá - second link lead me to this page (being a copy of MS documentation). Slightly below the half of that page called "Troubleshooting tile, toast, and badge notifications" there is a short paragraph titled "Errors when attempting to create a push notification channel", explaining three common errors that may occur:
The reason is missing Internet capability declaration! Quite different from the actual error message, isn't it?
Okay, so enable it. But there is one more small thing - do not forget to rebuild and redeploy your application for the change to come into play.