Minimum distance between two connectors in a high voltage PCB design
So, could I find a distance between both connectors in which the VCC+
  connector and VSS- connector will be safe from breakdown?


Yes, but it's already been done for you in the IPC specs the table below shows this. It might be best to use two separate 1 conductor connectors, instead of finding one that has both (although the connector wouldn't be keyed for polarity). Here is a breakdown of how to calculate spacing between PCB traces:


Source: http://www.smpspowersupply.com/ipc2221pcbclearance.html