The rules on page 21 clearly state the conditions needed to place a Power card. The only condition listed in the rules on when a Power has to be removed is when there are not enough Trickerion Shards in that specific slot.
If you learn that power, then learn a power of level 36 fame, then replace Path of Greatness, you would maintain the level 36 power (assuming it still has the required shards assigned to it), correct?
I have used 'Path of Greatness' before, though I do not remember the exact wording, and did play it in the same way. I see no reason to remove the newly learned Power card after 'Path of Greatness' is removed.
Though it may be worth mentioning that since the rulebook mentiones "If a slot already has a Power placed next to it, you must return it to your hand before placing a new Power there." it seems unlikely that 'Path of Greatness' can be replaced with this 36 Threshold Power card.