After I upgraded to WordPress to version 5.4.1, a “Site Health Status” box appeared on my dashboard. This tool suggested that I should install the Imagick PHP module. Previously image uploads were working fine. After installing Imagick, all image uploads failed with the above error.
After trying out various solutions, the thing that finally fixed it for me and got image uploads working again was to install the “ImageMagick Engine” plugin. I’m not really sure why. I currently have Imagick Engine configured to use the Imagick PHP module, but it also works if I untick the “Enable enhanced image engine” box.