La extensión hstore crea funciones que llaman código desde un objeto dinámico externo, lo que requiere privilegios de superusuario. Es por eso que la creación de la extensión hstore requiere privilegios de superusuario.
En cuanto a Heroku, tengo entendido que se están ejecutando con un módulo especial de lista blanca de extensiones, que permite a los usuarios crear ciertas extensiones aunque no sean superusuarios. Creo que se basa en este código:https://github.com/dimitri/pgextwlist. Puede intentar instalar ese código usted mismo si desea la misma funcionalidad en sus bases de datos.
