I am trying to embed the Web-to-Case form generated using Salesforce's native HTML generation tool in my SharePoint page but when I paste the generated HTML, Sharepoint gives me the following error:
"This embed code doesn't seem to work. We only support iframe based embeds."
Does this error mean I need to have this web form published elsewhere in order to embed it in the sharepoint page?
That's 1 option, yes. It could even be static html page you load somewhere on a side in the SharePoint server or you could publish it to Heroku or whatever (read here or here)
At the end of the day the Web-to-Case functionality is all about making a POST request to certain url with some parameters in the body. SF lets you generate a html form you can embed on any page & style however you want but out of the box thing is bit poor. It can include CAPTCHA but if you leak the target SF org’s ID in such form – you might be getting spam. Best would be to not use generated HTML but capture something in your server-side and make a HTTPS POST to SF server-side. There’s no authentication on it, if somebody attacks you best you can do is disable the feature in SF. If it's done silently server-side you can do some validations, maybe pass more parameters you don't want the user to see...