Pain in the toes while cycling using clipless shoes
In addition to getting the right size shoes. Make sure the cleats are adjusted correctly. It sounds like you're getting something similar to "black toe" experienced by hikers and runners. It's usually caused by their toes getting jammed to the front of their shoes (imagine walking down a steep incline). 

If your cleats are too far back people tend to point their toes down while pedaling. The cleats should be centered under the ball of your foot, depending on riding style/ experience, they can be moved forward or back by a few millimeters. in a perfect world every shop would have professional fitment analysis to take the guess work out of all this. This also happens if the saddle is too high, people don't realize this when making the switch to clipless pedals. 

What I use to tell clients when buying new clipless shoes is to make sure they are snug around your arch and heel, but you're able to wiggle your toes comfortably.