Definitely try a test piece first. Contact cement contains some chemicals that will destroy some plastics. If it does not then yes, rough up the plastic and the leather at the point of the bond. This still will probably not be a long time arrangement. Clear epoxy might be a much better choice, but it will not be flexible when cured. If it's a no bend or flex situation I would say the epoxy would be best.
Edit: I just reread your post. Plastic to Kydex. I don't think contact cement would last any time at all. Epoxy or rivets, Chicago screws, T nuts and bolts (small), or eyelets would be my choice I think. All but the epoxy would make it removable also.
Paul