Should I caulk the gap between a wood threshold and concrete?
I would use Quad sealant. It is paint-able or comes in colors.
I would use a paint stripper to remove as much paint as you can,  I like the citrus based strippers. Mask off the door jamb and the wood floor inside and apply the stripper, use gloves and a disposable brush.  After it does it's job of loosening the old paint you can scrape it all off. (It may take a couple of applications) You could also strip the brass threshold piece, it is removable, and polish it up.
Once you get as much old paint off as you can you sand smooth, fill any voids and sand again. Use a  the pointy end of a 5in1 tool to clean out the gap, you do not want any old paint, stripper or debris left in there.
The Quad can be applied before or after painting, it depends on if you can get it in the color to match your paint or you need to paint to match.
When you apply the Quad you need to mask off the concrete and the wood, it is tenacious stuff. (* The key is to practice first so you can get a feel for how much to apply, not to much*)
They recommend that you do not tool it, but i find you can smooth it if you dip your finger in a soapy water solution, or better, mist it with a spray bottle) and gently run you finger over the surface. Remove the tape immediately.