Depending on the class and wealth of the individual, they would seek advice of a university taught doctor (often sponsored by the church), a local physician or perhaps a herbal doctor. At his point it is important to not that medical care in the medieval period varied... alot. First I will deal with the elite university doctors who would have been able to access the medical texts which due to their cost were few and far between. Only wealthy citizens are likely to be able to afford the treatments. A respected opinion of the time (and one that you will find in medical texts) was that toothache was caused by the imbalance of the four humours: fire, earth, water and air. A popular treatment to fix this would be bloodletting and also the inhalation of smoke from various herbs, dependent on which humour the physician thought was causing the imbalance. Most of the medical texts I have found advise against tooth pulling unless the pain is severe and it is the last course of action. If the tooth had a fracture an early filling material had been invented (although it differs from doctor to doctor) an example I have found in Chirurgia Magna by Guy de Chauliac was composed of gall nuts, pig grease, mastic, myrrh, sulphur, camphor, beeswax, arsenic and asafoetida. This would be packed into the crack and the tooth wrapped in cloth. Advice of fasting and eating soft meat for the next 20 days was often given alongside. False teeth could also be created, most likely from cow bone, if a tooth was extracted and fixed in place by golden wire. Doctors would almost certainly try other herbal remedies as well as advising their patients to pray and carry charms.

Some medical texts if you're interested: Chirurgia magna attributed to Guy de Chauliac Rosa Anglica Medicinae by John of Gaddesden Compendium of Medicine by Gilbertus Anglicus

If you were poorer you would likely go to a local physician, most of what they woulld base their practice on is passed down during apprentices or learned through talking with other physicians. Bloodletting again would be common but herbal remedies and tooth extraction would be alot more popular. The Physicians of Myddfai is a welsh collection of herbal and folklore remedies and I'm sure the French would have a simliar ideas. I'll copy a couple of extracts so you get an idea of what it entails.

"Get an iron nail and engrave the following words theron, + agla + Sabaoth + athanatos + and insert the nail under the affected tooth. Then drive it into an oak tree, and whilst it remains there the toothache will not return. But you should carve on the tree with the nail the name of the man affected with toothache, repeating the following: By the power of the Father and these consecrated words, as thou enterest into this wood, so let the pain and disease depart from the tooth of the sufferer. Even so be it. Amen"

"whenever you wash, rub the inside of your ears with your fingers"

"Take the leaves of sage (Salvia officinalis), powder with as much again of salt, and make it into balls. Bake them till they are burnt and powder. Let your teeth be rubbed frequently therewith. It will render the teeth clean, white, and sweet"

I hope this helps, medieval dentistry is quite hard to pin down and give an exact answer.