I was also struggling with this error bout found a solution. If you want to use custom app on paid store, not dev store, you need to implement token exchange (for embedded app) or Authorization code grant (for BE apps) as described here: About token acquisition
Simply Using the client credentials grant works only for dev stores - If you try getting access token this way from paid store you will get error:
Oauth error shop_not_permitted: Client credentials cannot be performed on this shop.
This topic is also discussed here: Custom App Credentials - #9 by Donal-Shopify