As Stephwheel said in the comments, Icicle Spear is an egg move for Baxcalibur, so it can't learn it by level-up.
Now, there are two ways to get Icicle Spear on your Baxcalibur. The first, and the easier one is to use a Mirror Herb. They can be bought from the Cascarrafabranch of Delibird Presents. As per Bulbapedia:
In Pokémon Scarlet and Violet, if the player has a picnic with one Pokémon that holds a Mirror Herb and has an empty move slot, and another Pokémon that knows a move the first Pokémon can learn as an Egg Move, after the picnic the first Pokémon will learn that Egg Move, even if there is no matching Egg Group. This does not consume the Mirror Herb.
Simply catch a Pokemon with Icicle Spear, and that'll transfer on to your Baxcalibur by using the method above.
Otherwise, you'll need to get it the usual way by hatching a egg, a guide to which can be found here.
The Bulbapedia page for the Mirror Herb.
