SOLUTION BELOW
Was running into this error
Turns out, I had assumed the NOTION_TOKEN variable that we have to set in the workflows env variables was supposed to be the token described here - https://www.notion.so/Find-Your-Notion-Token-5da17a8df27a4fb290e9e3b5d9ba89c4. However, that is incorrect!
The NOTION_TOKEN is actually the Internal Integration Token that's described here - https://developers.notion.com/docs/getting-started#step-2-share-a-database-with-your-integration. You must manually create an integration for Notion Quick Add within your workspace to get the Internal Intergration Token which should be used for the env variable NOTION_TOKEN.
Hope this helps somebody!
Thanks to @alf for the nudge in the right direction.