I haven’t tested this myself yet, but we are planning to do this too so it’s on the product backlog.
My initial thought would be to subscribe to the SHOP_UPDATE webhook for each store that installs your app I suspect it will be triggered on a plan change, so you just need to then write the logic to parse the notification and see if it is related to the shop plan.
I’ve pasted the URL to the docs below.
Let us know hi you go!
https://shopify.dev/api/admin/graphql/reference/events/webhooksubscriptiontopic