None of this rambling will likely help at all so consider what follows little more than the rants of a grumpy tech guy.
MSPaint along with many other utilities is now a "managed" application. In some cases, initial slow application response and other issues can be attributed to starting "managed" applications using Windows "native" APIs. Many of MSFT's utilities have a stub native program whose sole purpose is the start the "managed" application. At some point starting the "managed" application directly instead of using the stub when using Windows native APIs could correct these issues. However, now it appears that starting the "managed" application directly will not work at all.
For what it's worth "managed" applications are in the maze of folders under "C:\Program Files\WindowsApps" assuming "C:" is your system drive of course. For example, Notepad.exe is in the "C:\Program Files\WindowsApps\Microsoft.WindowsNotepad_11.2306.15.0_x64__8wekyb3d8bbwe\Notepad" on my system. Keep in mind that the "managed" version sometimes has a different file name than the "native" stub. Also, strange Windows application behaviors are almost impossible to predict from Windows update to Windows update.
For better and often worse Windows ain't what it used to be.