Thanks for pointing me to the general solution/root of the issue.
Unfortunately, I still can't make it work, even after trying a lot of different suggestions including following the official Alfred advice (https://www.alfredapp.com/help/kb/python-2-monterey/), installing and setting up pyenv. And I have tried reinstalling several workflows, including Convert (https://github.com/alfredapp/updated-third-party-python2-workflows) afterwards.
Then, I have tried pointing bash to the pyenv 2.7 version instead of the also installed 3.9.12 (including by following the last advice here https://stackoverflow.com/questions/15285592/how-to-set-default-python-version-in-terminal-on-os-x-10-6-8). Now, when I write "python -V" in a fresh terminal session, it does show Python 2.7.18. But the workflows still don't work.
My hunch is that it is because I have several Python versions installed (and installed in different ways including via Homebrew and via pyenv).
Is there anything I can re-/uninstall or something to make things work (e.g., Python, pyenv, Alfred), I wonder?