Some car rentals won't let you drive to another country, in case it gets stolen, it's out of their jurisdiction
Try avis and ask them for green card(its an insurance on the car for driving overseas from Poland)I never had a problem driving to ukraine.belarus,russia,and slovakia with that