Looks like you have an error here :
<permission android:protectionLevel="signature"
android:name="org.example.app.permission.C2D_MESSAGE" />
<uses-permission android:name="com.example.app.permission.C2D_MESSAGE" />
I'm assuming the correct value is org.example.app
(based on the rest of the manifest), so it should be :
<permission android:protectionLevel="signature"
android:name="org.example.app.permission.C2D_MESSAGE" />
<uses-permission android:name="org.example.app.permission.C2D_MESSAGE" />
The reason it works on the emulator and not on the device could be that the device has an older Android version. This error affects only 2.x Android devices.