After hours of trial and error I fixed it!
The problem was the one of the Windows icons I used in the Command AppBarButton. Apparently that icon does work on Windows 10 but not on Windows Phone 10 (don't know yet which icon is exactly the culprit, but we are talking about e.g. a standard undo icon so it is pretty dumb that it does not work on Windows Phone).
Also deploying UWP app packages seems really buggy in Visual Studio, I almost always need to 'clean' and 'rebuild' the solution before it works. :?