custom taxonomies label in hebrew in WordPress

You can just wrap the english label name with the translation function __( 'City', extdomain' ) , and put the hebrew version in your translation file.

Reference: http://codex.wordpress.org/I18n_for_WordPress_Developers