Thank you very much for your help @deanishe. I have found an old comment by @Andrew stating that Alfred uses NSRegularExpression for regex search and replace and that \n in the substitution field is not recognized because the \ character is taken as a literal. The solution offered by @Andrew is to use Alt+Return instead. I have tried it and it works, but now there is a second problem: once you input Alt+Return in the substitution field there is no way to delete it because it doesn't appear in the field, so I had to delete that element in the workflow and recreate it.
The post where Andrew talks about it is here: