Heroku buttonがいつの間にかGithubプライベートリポジトリでも使えるようになっていました。

設定方法はパブリックなリポジトリのボタンと少し違っていて、ボタンのリンクに template={リポジトリへのURL} をつける必要があります。
Markdownならこう書きます。

[![Deploy](https://www.herokucdn.com/deploy/button.png)](https://heroku.com/deploy?template=https://github.com/{Githubのid}/{リポジトリ名})

また、デプロイにはHerokuアカウントとプライベートリポジトリへのアクセス権があるGithubアカウントを連携させておく必要があります。
連携させていない状態でHeroku buttonを使うと、以下のような画面が表示されます。赤丸部分をクリックすると、デプロイ画面に進みます。