@Benjamin Kokholm Broen,Thanks for posting in Q&A.
From your description, I know that you encountered an issue that when tried to install a VPP app on DEP enrolled device.
I have done some research and here are some methods you can refer.
1.You can change the license type from User to Device in Intune > Apps > iOS > app > Assignments
2.If the issue still exists, please try to revoke and reassign the app lichens.
At the same time, the following blog may provide a solution. We can refer to it.
https://www.techoberoi.com/post/failed-can-t-find-vpp-license-for-app-0x87d13b95
Non-official, just for reference.
Hope above information will 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.