Leaving a full answer here for post-release Drupal searchers.
The message "translation is not supported" refers to the content of the fields. The content in this case is not stored, ergo, cannot be translated - unlike, for example any node title or image description.
To translate content like field contents, the required modules are languages & content translation. In your case, you want to actually translate the field titles. This is classed as configuration translation which requires the module of the same name, and that in turn depends on interface translation. So basically, you'll have all of the core modules enabled to perform this task (as obviously you will be translating content as well, right?)
When you have enabled the required modules, you will need to download the .po translation file from .drupal.org and import them in the area User interface translation > Import. Also you can check for updates to your module interface translations under Reports > Available translation updates.
Translating a contact form's fields then is done automatically (if the language file provided for that). Translating the contact form's configurable items is a matter of visiting Structure > Contact forms and selecting translate on the edit/context menu of the form required, whereby you can translate the auto-reply etc.
