Galera... depois de muitas tentativas, conseguimos resolver o problema aqui. Pegamos um DVD Recovery do Window 8.1 de outra máquina qualquer e colocamos na unidade quando estava pedindo a famosa tecla F4. Nisso, apareceu a tela pedindo para pressionar uma tecla. O note travou e precisamos desligar no botão. Depois, ligamos novamente, com o DVD na unidade e apareceu para pressionar outra vez.
Pressionamos varias teclas e ele travou novamente, então retiramos o DVD, e nessa hora apareceu uma tela azul com várias opções. Uma delas era para entrar no gerenciador da firmware (BIOS). Depois de entrar na bios, retiramos as travas do Security Boot e alteramos a ordem de boot. Agora o note inicia normalmente e até aparece as opções F2 e F4 na inicialização.
Obs.: Como já tínhamos instalado o windows 7 no HD (em outra máquina) e rodado o sysprep, ele concluíu a instalação normalmente.
Não sei se só com o DVD do W8.1 dá certo, usamos o Recovery de um Desktop HP.