The quests to unlock the HM primals are in the same order as the relic reborn quest requires them. There's no room for confusion as you just do the quests and get the credit towards your relic as you go.

With regards to the aetheryte in the mines, you need to run ALL the way through the mines and enter that tunnel from the other end. Breadcrumbs aren't lacking, just look at the map.