Conversion is too soft a word for what will have to be done, it is more than likely going to be a rework.
Somethings you need to figure out:
I would like to add a ceiling fan/light to one of the receptacles
A ceiling fan is far heavier than a recessed can light and thus needs additional support. The recessed light box will need to be replaced with a special box that braces itself into a ceiling joist or into a wooden block between two ceiling joists. Looking at how the recessed light box is being fastened into the ceiling will tell you how to do this.
and convert the other to a track light with its own light switch control.
This can be done but even in the best case scenario, you will need to run an additional cable from the switch gang box to one of the luminaires. This is of course assuming that the cable coming from the breaker is coming into the switch box.
It becomes more complicated if the power to the breaker is coming into one of the two lights. In this instance you would need to run a 3 wire and ground cable from the switch box to the light with the power line coming in:
NOTE: All of this of course is assuming that if one of these happens to be a fan/light combo, then the fan and light will be wired to turn on with a single switch, rather than separate switches for each function.
NOTE 2: This also assumes that you have already have a double gang box for installing two switches. If you do not have one then you will need to open up the wall and install one.
NOTE 3: The following diagrams assume equipment grounds are properly wired throughout.
You could replace both switches with home automation smart switches, wire the lights "always on", but then put micro relay controllers or even micro dimmers in the lights' individual junction boxes. Then program the physical switches to control the lights you want.
No new wiring needed. And you can grow the system down the road with remote controllers, motion, etc.
Best Answer
That sounds like your standard basic electrical bodge job, where it once worked, and then some homeowner or handyman got in there and mucked it up good-n-plenty. God knows what else could be wrong in there. Or what else that menace has done!
I gather all this sparky stuff is new to you. You may be better off bringing in a pro to correct that blunder and search for other flaws. They have a fair chance of correcting a dangerous situation.
If you want to take it on yourself, good, but take your time (you don't want to become that menace). Learning electrical is a wide mountain (but not a steep one). I'd hit the library and look at electrical books (adult nonfiction, section 621.3192) and browse a few and find one that speaks your language. Then indulge in reading most of it. That'll establish well-rounded knowledge on the subject, something Google is awful at... and then we or Google can fill in the gaps.