It is possible to take the ferry from Port Kavkaz to Kerch on Crimea, Ukraine. The ferry goes approximately every 2 hours until 4PM, whereas tickets can be bought until 30min before departure. Border controls will be done before entering the boat. The rate is 160 Russian Roubles (2012), for up to 25kg of luggage.
Drivers pay for each passenger, so you will have to buy a ticket at the office. You can ask drivers while you wait to be let on the boat. Once off the boat, your passport will be checked again; after that you can hitch easily on the road to Kerch. There is also a bus station at the terminal in Ukraine in case you have no luck.