Fine, you win. I had a look for myself.
I did a Google search for "Super Mario Bros. (1985)(Nintendo)(J).fds" without the quotes, and the first hit provided a download for a ROM that was 65,516 bytes and had the MD5 sum listed on the page. I have no idea what ROMs you may have been testing that do not match up. The patch applied perfectly.
If your ROM is missing a header, then your ROM will be 65,500 bytes. If your ROM is already 65,516 bytes then you are having some other problem.
If you want to add a header, then you can use your hex editor to copy any 16 bytes of the file and paste them at the start of your ROM to make the file 65,516 bytes in length. It makes no difference what those 16 bytes contain in this case.