先に結論です。
並列化は、「Procfile で worker を複数のプロセスとして起動します」
PHP なら以下で、複数プロセス(例では3件）を起動できます。
worker: php worker.php | php worker.php | php worker.php
分かってみれば、実に単純な設定です…。
Heroku のドキュメントに載せてくれてもいいようなものですが、ありません（見つけられませんでした）…。
このあたりは、サーバ・エンジニアの知識があれば当然のことかも知れませんが…。
Paas を使う開発者にとっては、そのあたり、ドキュメントがないと非常に不利と思いました。
詳しくは長文になるのでブログ（「Heroku: worker のプロセスを増やす（分散）する方法(for RabbitMQ)」）を見てください。
RabbitMQ で行う処理を、1つの Worker で並列処理できないかということで調査した結果になります。