Is your Pixel's battery still able to last between charges the way it usually has? if you've seen a significant drop in performance that could indicate the battery is failing but if not I wouldn't think the battery itself is the problem. A Pixel 4a will be a couple of years old so the battery is at a point where it might possibly start to decline a bit, that's inevitable. But it should be able to give you a few more years of service.
Given all the things you're already tried, you can probably rule out the battery, the cabling, and the power adapters as being the source of the problem. It is odd you're seeing that charging message when you plug it in but it's not actually charging. That might indicate there's some kind of glitch with your phone's internal charging. Note in this instance it will be relative to the lower levels of your phone, at the stage where the actual Android operating system interacts directly with the phone's hardware circuitry. We typically only interact with the user-friendly user interface that runs on top of all that. When a phone is charging itself, that's a function involving power transfers in that lower level. Anyway, try wiping your phone's system cache and see if that clears up the problem. You'll need to boot your phone up into its Recovery Mode, a multi-step process (Boot up into Fastboot, then select Recovery)
https://www.hardreset.info/devices/google/google-pixel-4a/recovery-mode/
https://clearcachewiki.com/guides/how-to-wipe-cache-partition-on-google-pixel-4a/
Wiping the system cache won't delete anything vital, nor any of your data. (cache files are all temporary).
When you did a Factory Reset, keep in mind that all it does is wipe the user data partition clean. It has no affect at all on the operating system itself so while that did rule out some kind of third-party software problem or one-off Settings menu quirk, if (big if) the problem is OS related than let's hope this does works.
