Small update: I nuked all presence of java and maven with dnf autoremove
and then reinstalled maven and it did indeed install all the necessary
packages and now I also see the jre folder in the /usr/lib/jvm/... but
still! the same error. What is more interesting though is that if I
switch to root user, maven suddenly works. So it must be something going
on with my user shell. Investigating further..