Just in case someone else wants to try this as well, we found a download link for previous versions of Postman and I tried a few of them pinpointing which one is the latest working under Catalina. For me, it was Postman v11.58.3.
Here’s the link to download it: https://dl.pstmn.io/download/version/11.58.3/osx
Unfortunately I fear it might auto-update as soon as I close it (it already downloaded updates after first opening)… unless someone else figures out how to disable it from auto-updating, then please let me know!