Can't push refs to remote try running pull first to integrate your changes

You get this try running pull first to integrate your changes whenever your local branch and your remote branch are not on the same point, before your changes.

remote branch commits : A -> B -> C -> D
local branch commits  : A -> B -> C -> Local_Commits 

Now clearly, there's a change D that you don't have integrated locally. So you need to rebase, then push, which will lead to the following.

remote branch commits : A -> B -> C -> D
local branch commits  : A -> B -> C -> D -> Local_Commits 

To solve your issue, do the following

git pull --rebase origin branchname
git push origin branchname

I was getting this message in my Azure DevOps Repos environment because the server had a branch policy on the master branch that requires pull request approval and I was trying to push to master directly. Even after pull and rebase the same message appears. I don't think VS Code really knows how to interpret this specific error coming back from the server so it gives the generic message. If I try the same push with git directly it shows a remote rejected error that explains the problem. So my answer only applies in this 1 narrow case, but it can definitely cause the same error message to appear when pushing in VS Code.