A extensão hstore cria funções que chamam o código de um objeto dinâmico externo, que requer privilégio de superusuário. É por isso que criar a extensão hstore requer privilégio de superusuário.

Quanto ao Heroku, entendo que eles estão rodando com um módulo especial de lista de permissões de extensão, que permite aos usuários criar certas extensões mesmo que não sejam superusuários. Acredito que seja baseado neste código:https://github.com/dimitri/pgextwlist. Você pode tentar instalar esse código sozinho se quiser a mesma funcionalidade em seus bancos de dados.