Lack of mathematical training for a CS Ph.D
Lack of mathematical training is a gap, but not what I would consider a red flag, if you have strength enough in other areas.  The key is whether I, evaluating your application, would think: "This person can't handle math" vs. "This person did other things besides math."  

It is definitely a good thing that you are increasing your training: a MOOC will likely not make a big difference on paper, but if it's making a real difference for you intellectually, that matters too. Furthermore, a good mental mathematical tool-kit will make your life easier in many ways (including detecting when you shouldn't believe something just because it has math).  

As for the question of whether to start with a Masters: that really depends on where you are and where you are trying to go.  For example, in the US, many Ph.D. programs literally or effectively start with a Masters, so it might be redundant (though the MOOCs or any other prep work will allow you to do less remedial work as part of it).  In Europe, on the other hand, most Ph.D. programs assume you already have a Masters, so it's pretty mandatory to start there.  Another thing that you might consider is to apply to both, starting with the Ph.D. if you get in, and burnishing your credentials in a Masters first if you don't.