After struggling for a bit, then giving up, then struggling a bit again, I have discovered a simple way to get some Alfred workflows working around quarantine in Catalina. When a new/updated workflow fails, cancel the warning then run this.

xattr -dr com.apple.quarantine ~/Library/Application\ Support/Alfred/Alfred.alfredpreferences/workflows