I was able to solve this issue using a solution from another similar question:
-
Downloaded Android Studio
-
Installed Android Studio. It found the folder with the Android SDK installed, I did not change it.
-
Removed the license from / android-sdk-windows / licenses.
-
Accepted the license in UE4 again.
This is from a comment on this page: https://answers.unrealengine.com/questions/718698/accept-the-license-agreements.html