This is what I see for permissions on dnf on my f38 system:
$ ls -lZ /usr/bin/dnf-3
-rwxr-xr-x. 1 root root system_u:object_r:rpm_exec_t:s0 2092 Sep 20 01:00 /usr/bin/dnf-3*
$ ls -lZ /usr/bin/dnf
lrwxrwxrwx. 1 root root system_u:object_r:bin_t:s0 5 Sep 20 01:00 /usr/bin/dnf -> dnf-3*
Is that what you see?
yep, looks the same on my system
Given its a SElinux issue (isn’t it) I wonder if relabling the SElinux labels will help?
sudo touch /.autorelabel
sudo reboot
Do you have additional security tools installed on your system?
Since this isn’t in the steps described in Upgrading with DNF, at least for the standard install process, and this fixed things for the OP, I guess I’m wondering whether we should all be doing this immediately have doing the sudo dnf upgrade --refresh step. Are you suggesting that we should?
Thanks!
john
(this hasn’t fixed it for OP)
Oh! Sorry for the misunderstanding. 
After looking a bit closer here, I agree with @barryascott and think you have an selinux permissions problem on your current system.
Did you try his suggestion to run fixfiles?
It is often the case that fixes to the upgrade process are ship late in the day.
For example there is a fix for upgrading Raspberry Pi in f38 that is required.
So I follow the process that you MUST do a dnf update --refresh before a system
upgrade. It used to be recommended part of the upgrade process.
It still is!
Re-reading my post, I meant to say “immediately after doing the dnf update --refresh step”.
Thanks for getting back to me on this.
damn, that fixed it.
I have no clue about SElinux, so I couldn’d have figured it out myself.
Thanks