Since Power Query is loading its data to a worksheet, that worksheet is going to need to be unprotected in order to take the changes. The simplest way to fix this is probably to unprotect the worksheet and hide it, so that your users won't see it.
If you do need the user to be able to see that table, you can pull it off using VBA. The basic process you need is:
-Unprotect the worksheet that holds the query
-Refresh the query
-Re-protect the worksheet
You should be able to record a macro to do this.