You should check the eligibility criteria directly with the universities you want to apply to. Try to contact possible supervisors and comment on your particular background and research ideas.
From my experience in the European context, the most important part of your PhD application is your proposed project. I know many PhD candidates with not such great results in their previous studies and they have been accepted into their programmes. Of course, having more that average results could be an asset in your application but it is not the most determinant factor to be accepted. Although, it could be a requirement for certain scholarships.
You cannot change the grades you have obtained but you could boost your curriculum by getting practical experience in your field (another relevant factor depending on your area). A friend of mine did another master to appear as a more apt candidate. I would not recommend such investment of time, money, and effort when you could always make your case in your motivation letter remarking your research oriented attitude and highlighting your excellent research results.
Good luck!