The ThirdParty folder has a Python folder in it, which looks to just be a regular python install. Sometimes this happens because the developer wants to make sure that a required python version is present on the system, without making it an explicit requirement.
I just took the zipped python distribution from above and extracted it into that location, replacing the entire structure (they match exactly). I also replaced the python39.dll in the other locations suggested above.
Hope that helps.
(This got UE5 to start, and I can create projects, but I have run into additional problems getting it to build that I haven’t resolved yet. I’m a hair’s breadth from just switching to linux permanently.)
Edit: Just replacing the DLLs wasn’t enough to fix it on my machine, but certainly that’s a less invasive way to start. I’m just sharing what worked for me!