@Frenzel, Sophia, Thanks for posting in Q&A. Agree with Rahul, Dependencies are applicable only when installing the Win32 app on the device. Dependencies are not applicable for uninstalling a Win32 app. And the app will not be removed automatically.
For the dependent app, it is run as system account. It seems the install behavior of the win32 app is set as user. So when the uninstall script run, it fails with permission issue to uninstall the first package.
For this situation, I think you can deploy a separate PowerShell script and set "Run this script using the logged on credentials" as no to let is run under system account to remove the files in package 1.
https://video2.skills-academy.com/en-us/mem/intune/apps/intune-management-extension
As another method, you can deploy the dependent app via Intune win32 app as well. And add the user or device group under uninstall assignment of both apps under Intune to remove them.
Hope the above information can help.
If the answer is helpful, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.