Under Privacy -> Health the App Messages is listed as an App accessing my Health data, and in the Health App, Massages is listed as a Source.
How do I revoke those permissions?
And is there a way to delete the Health App altogether?
You can't delete the health.app without jail breaking as it isn't listed in the list or delete able built in apps.
Open the Health app and tap the Sources tab.
Tap an app or device.
Then you can disable it as a source.