... the reward is now a function of action taken in state given the sampled goal.
I believe the action taken is that from the original goal, not from the newly sampled goal (as you say you understand). Otherwise I think you have everything more or less correct.
We see in the first block of the algorithm, that each action $a_t$, given the current goal, g, results in the reward, $r_t$ (as usual). This is stored, along with the new state $s_{t+1}$ concatenated with the current goal (shown by the ||
symbol). This is highlighted as being standard experience replay.
In the second block, using the sampled (virtual) goals $g'$, we receive a virtual reward for our performance using the same action as previously $a_t$. This is repeated for some number of simulated goals, selected by a sampling strategy, of which several are discussed in Section 4.5.
I myself was wondering how many replays are sampled, as it seems that the key there is to sample enough, so that the buffer itself sees the right balance of additional goals (to reduce the reward density), but not so much that the virtual HER recordings from the second for-loop do not outnumber the real performed goal-action pairs from the first loop. In the paper (Section 4.5), this seems to be around the $k=8$ mark, where $k$ is the ratio of sampled/virtual goals to the original goals.
So I believe the sampled goals that are indeed visited states from the original goal, would indeed receive a non-negative reward.
I think the following is a key statement to help explain the intuition:
Notice that the goal being pursued influences the agent's actions but not the environment dynamics and therefore we can replay each trajectory with an arbitrary goal assuming we have an off-policy RL algorithm like DQN ...
This is very true in life. Imagine you try to throw a frisbee straight across a field to a friend. It doesn't make it, instead flying off to the right. Although you failed, you could learn that the wind is perhaps blowing left to right. If that had just so happened to be the task at hand, you would've received some positive reward for it!
The authors sample many additional goals, which in my analogy, may be the flight dynamics of that particular frisbee, the air density/humidity etc.
The main contribution of this paper, is a method to increase the density of the reward function i.e. to reduce how sparse the reward is for the model while training. Sampling these additional goals after each attempt (failed or otherwise) gives the framework the opportunity to teach the model something in each episode.
In the grid-based example, if for example the agent doesn't reach the final goal (as its original goal), it records -1 to the replay buffer. Then other goals are sampled from the possible next steps according to a sampling strategy, $\mathbb{S}$. For If you were close to the goal, it would make sense that sampling from future states selected at random from the same episode - after the transition - that you would likely end up at the goal. It is important here to realise that the goal has changed, which allows reward to be received. I point this out because the goal usually doesn't change in grid-based games; however, the experiments in the paper were performed on a robotic arm with 7-DOF in continuous space (only the reward was discrete).
EDIT
Below is a sketch of an example path, where we reach the final goal after 10 transitions (blue arrows). I set $k = 4$, so in each of the states $s_t$, we also have 4 randomly selected goals. We then take the corresponding action $a_t$ for the current state, which is the blue arrow. If the randomly sampled goal, $g'$, happens to be the same as $s_{t+1}$, we get a non-negative reward - these are the orange arrows. Otherwise, a negative reward is returned: the green arrows.

This is an example of the random sampling strategy, as my sampled goals $G$, are states that have been encountered in the whole training procesdure (not just the current episode), even though you cannot see it in my sketch.
So here we see there are 4 sampled goals, whch do indeed return non-negative reward. That was chance. The authors do say that:
In the simplest version of our algorithm we repla each trakectory with the goal $m(s_T)$, i.e. the goal which is achieved in the final state of the episode.
In that case, it would mean $k=1$ and is always simply where the episode ended. This would mean negative rewards in the HER portion of the algorithm for all time steps exluding the final, $t=T$, where we would reach the sampled goal.
That would indeed equate to the model having learned from an otherwise failed episode. In every single episode!