What's this new crafting material I suddenly need, and how do I get it?
It's called Shards of a Star, and you probably won't be getting enough for an upgrade anytime soon. Your first opportunity to score some of this mystery metal is by winning the Pharaoh's Shadow fights that pop up every so often as you explore Thebes and the nearby environs. But even winning one of these fights only nets you three stones, and you need twenty for your first upgrade.
Given that these fights aren't exactly slam dunks, and they only come about once every fifteen minutes, this isn't a very effective way to fill your pockets. Better is to follow the main questline (Curse of the Pharaohs into No Honor Among Thieves into The Lady of Grace). As part of The Lady of Grace, Bayek will pass through into the Afterlife of Aaru, where you'll be able to collect tons of starmetal by looting chests, raiding quarries, and killing giant scorpions (each scorpion grants 2 shards, and can be killed by a single predator arrow to the faceparts. Much easier than the Shadow fights).
Once you start moving through the Afterlifes in earnest, check out Nut's Gift in Aaru, the Crocodile Lair in Aten, the Halls of Serqet in the Duat, and Orion's Crater in Heb Sed. Each one contains a white chest with 20 shards, and often many smaller caches nearby.
So, are the Pharaoh's Shadow fights worth doing?
Only if it's convenient. If you're in the middle of something else, don't sweat about dropping everything to rush pharaohward, but if you happen to be in the area, they do offer decent experience, and that miniscule-but-non-zero amount of starmetal. The most difficult thing about these fights is not the fight itself, but the time limit. These powerful enemies require good use of dodge and parry skills, but if you don't also pour on tons of damage, they'll simply disappear on you. Poison weapons and adrenaline building weapons can both be helpful in meeting your DPS goals here.
The other benefit to doing these fights is that these Shadows use the same moves and attack patterns as their namesakes, making them good practice for taking on the actual Pharaohs. Then again, fighting the actual Pharaohs is also good practice for fighting the actual Pharaohs.
Which new Abilities should I get first?
Overpower Fury is probably the must-get of the new batch. With it, using Overpower attacks now heals Bayek and allows him to shrug off status effects, creating a nigh-unstoppable cycle of destruction and healing. Past that, consider the Favor of Osiris, which slowly (but not too slowly) replenishes your arrows and tools while in the Afterlifes. It's handy on its own, it and can make any of the Pharaoh fights a cake walk, as you use warrior bow shots to inflict damage and raise adrenaline, Overpower when your meter fills, and then repeat the process with a magically refilling quiver.