Is it safe to "salt bake" using ice cream rock salt?
There are some kinds of rock salt that are meant for consumption ("food-grade"), and recipes like that salt-baked shrimp intend you to use that sort. While you're not directly eating the salt, it does come into contact with the shrimp, and there's water there to spread things around, so really, you are eating a bit of it. Even if there's not a safety issue (some things could conceivably be toxic) it might well taste bad, and some of the flavor does get into your food. You wouldn't be able to count on this being reliably the same from box to box, either; if it's not food grade, there could be plenty of variety in what the extra minerals are. Sometimes it might be fine, and sometimes it might taste awful.

It can be hard to find food-grade rock salt, though, so if that's an issue, you might consider switching to other salt-crusted recipes that use kosher salt. Especially with shrimp, this should be manageable, because it'll be on the outside of the shells, so though the salt will dissolve more easily, once you peel them it shouldn't be horribly salty.