It should be in the grouping of Permanent Powers. This is the same group as any Paragon Reward Powers or any other MTX Powers (Ninja Jump, Pocket D TP, ect. ...). The listing will be below the Temporary Powers.
EDIT: Also make sure you've Trained to Level 4. Just because you've dinged 4, doesn't mean you are Level 4. Once you've Trained to Level 4, any Powers that unlock will become available.
Thank you for the time...
@Travlr (Main) / @Tymers Realm (Test) 
Also, you may need to log out and then log back in to see the purchase. Sometimes purchases from the market don't show up until you have logged out and then logged back in.
I always exit to the desktop and restart the launcher and then the game just to be safe.
If the game spit out 20 dollar bills people would complain that they weren't sequentially numbered. If they were sequentially numbered people would complain that they weren't random enough.
Black Pebble is my new hero.
Found it.. thanks.
I bought the beast travel power, but so far it hasn't appeared in game. It says you can choose it once you reach level 4 but it does not appear in the list of extra powers.