Unable to remove directory "bin\Release\app.publish\". Access to the path 'AzureStartupTest.Azure.cspkg' is denied.Turns out someone is holding on to that file!!
When you create an Azure package, VS opens a file explorer window showing you the published files. You should close this explorer window before you run the package command again. It also turns out that Internet Explorer holds on to the file if you've uploaded it through the Azure management portal. If you refresh (F5) the management portal, IE lets go of the file and you can run the package command again without problems.
It seems I'm not the only one on the Internet running into this problem. I found some shady advice out there, such as rebooting your computer or disabling the antivirus to make the problem go away. I would recommend neither. With the aforementioned trick you can safely re-enable your antivirus and get back to work.