May be it's too late, but here is the result of my research. I haven't found the price for the line Navbul mentioned by the op, but there is another company that connects Varna (Bulgaria) and Batumi/Poti (Georgia) ports: UKRFerry
The price for this route is from 120 USD per person (depending on the accomodation chosen) USD and 350 USD per car.