The problem with Avoda Zara is if they tell you that it is coming from a specific Avoda Zara. The Rashba was Metzaded to be Mattir real Kishuf, since Nitten Reshus Lerofe Lerapos so it isn’t Mak’chish Pamalye shel Maale.
Non-natural remedies were never Assur when they worked. The Gemara has plenty of such remedies. Not understanding something does not make it Kishuf.