It's always worth checking the md5, but it's not something you do in recovery. You check the checksum of the downloaded file matches that on the download site before attempting to install it. There is a thread about this in the FAQs section of the forum.
However, as long as you don't have a corrupt sd card (e.g. a cheap card that isn't what it is supposed to be) it's not so likely that both are bad downloads.
Has this particular recovery ever flashed anything your phone? And do you have signature verification off (off is what you want)? Though if that's the problem I'd expect it to say so.
I don't have a S4, so am not familiar with ROMs for it. But if you want someone to comment on those you need to provide links rather than names, in case for example you are downloading files for the wrong S4 version.