I bought a EVGA GTX 1080 from a friend and I'm trying to nail down the correct power cables for it. I bought a pair of cables from ebay that I thought would fit and they do not.

PSU is made by Ultra, model HS-650BR and it has two 8 pin power connectors labeled "PCI-E Connector" on it (Pic attached), and the cables I bought are labeled EVGA VGA G3 (also Pic attached). There's an 8 pin on one end and a 6 +2 on the other, and both of these plug into the graphics card nicely.

The problem is on the other end at the PSU. Neither end wants to fit there. Is my PSU obscure and non-standard?

What type of cable is correct? Is there any way I can modify the ones I have to work?

If the PSU you already have have 2 PCIE wires, those are the ones you plug into the EVGA GPU
 
Or if it does not have PCI-e cable, you have to buy cables made for your brand of PSU
May want to consider getting an EVGA  or a seasonic gold 650-850 PSU
Do not cheap out on a PSU
 
I did not find a  Ultra, model HS-650BR  on ebay, you can try the manufactures site and get a cable.

 

 
The Blow Cables are NOT From your Power Supply DO NOT USE THEM.
 They are ONLY for use on an EVGA Power Supply.

 
If you do not have the Cables that came with your Power Supply then you will need to Buy a New Power Supply.
You must replace All your Old Power Supply Cables and replace them with the Cables that Come with the New Power Supply.

Eagle Lake Wood
Here's the PSU -
also uploaded a Pic of the connector on the PSU. Is the female PCIE connector on my PSU non-standard? Do manufacturers take liberty with making their own connector on the PSU side?

YES and you Can Not Mix Them.
The Device you are plugging them into is Standard but the Power Supply End is NOT Standard.
Power Supply is to old now and you most likely will not be able to get the correct cables for it.
https://www.amazon.com/Ultra-U12-42466-Modular-Supply-SLI-Ready/dp/B00ITA1QGU

Seasonic and EVGA seem to have good reputations for power supplies.  What is your budget?

If you can wait until next Wednesday, EVGA has some really good deal on their B-stock PSUs.
The sale price and often with free shipping on several PSUs on Wednesday.
I have bought several, 650 to 1000w and only had one I had to send back.
 
EVGA, Seasonic, XFX pro series. I even have an Antec platinum that has been good to me over the years.
Best advice do not cheap out, go gold or platinum. Better quality and save on energy cost. 
Here is EVGA's b-stock page
https://www.evga.com/prod...roductlist.aspx?type=8