Hi, welcome to the forum

It is definitely worth changing the gravel. All bottom dwellers prefer it.
It will make a mess. If you have a large container where you can house the fish for a few hours, it is worth removing them for the duration. (I have a fish-only dustbin I use for things like this

)If you don't, you'll have to do it with the fish in there so be a slow and careful as you can so you don't stress the fish too much.
Firstly, don't feed the fish the day before. And thoroughly wash the sand before you start as some types have a lot of dust and will need to be washed well.
On changeover day, remove some water into the container and place the fish in there. If you can use a large net placed in the front corner and use your hand to herd the fish into the net it will cause least stress. If there are any live plants, put them in the container as well. Cover the container as stressed fish will jump.
Turn off the heater and filter and scoop out the gravel. There will be a lot of muck in the gravel so you may need to remove a lot of water afterwards. Then place the sand in the tank and refill, planting any plants when there is a few inches of water. Pouring water straight in will make a crater. There are ways to prevent this, such as putting a plate or saucer on the sand and pouring the water onto that; loosely wrapping a plastic bag round the hose if you use one to refill; if you use a bucket to refill, pour the water through a colander so there are many water streams rather than one large one (I use a 170 ml yogurt pot with a
lot of holes stabbed in it with a knitting needle). Before the tank is completely full, put the fish and the water they are in back in the tank and then fill right up.
Don't feed the fish that day or the day after, then feed half portions for a few days. Monitor the ammonia and nitrite levels daily for a week, and do a water change if either show above zero. The gravel in there now contains a lot of good bacteria which you will lose when you remove it. Reducing the amount of food reduces the amount of ammonia the fish make. I changed from gravel to sand a few years ago and never saw any ammonia or nitrite by doing this.
The cheapest sand is play sand. It is free from any contamination - it has to be because children will eat some of the sand. But is does tend to be quite dusty. If you would rather go with a sand made for aquariums, check is does not alter hardness or pH - there are some sands made from crushed coral, limestone etc which are intended for use with hard water fish which will alter the water chemistry.
I need to make a comment about the fish you have an intend; it is not a criticism, rather what is best for the fish. Rather than getting kuhli or weather loaches you do need to get at least 4 more yoyo loaches. These are shoaling fish which need to be in a group of at least 6. So do the bleeding heart tetras.