Hi Monique,
Are you enabling the 'recreate repository' toggle switch in the native builder, if so it's wroth dsiabling that option and trying again.
If that doesn't work it also seems like this might be related to the github token you are using, does the supplied token have access to the specific repo where your template is stored?
Also worth checking if your token has access to read, write and create new repos?
I would also try Marcel's suggestion as that skip having to push to Github and likely solve your issue.
We don't let the native builder commit to the repository directly. Instead, we let the builder output to a local folder, which is a clone of the GitHub repo, using any git client like GitHub Desktop, VS code, cmd line. The first time you will need to create a new repo from the local folder.
After the build completes we commit and push the repo ourselves. Which in our case triggers the native app build in Bitrise.
This also allows us to check the build output first.
Here is the change I had to make in github.