Ok, hab die Lösung gefunden, falls es noch mal jemanden auf den Fuss fällt:
Manuell unter PHPMyAdmin
CREATE TABLE wp_woocommerce_tax_rate_locations (
location_id bigint(20) NOT NULL,
location_code varchar(255) NOT NULL,
tax_rate_id bigint(20) NOT NULL,
location_type varchar(40) NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
diese Tabelle anlegen und danach in den WooCommerce Mehrwertsteuereinstellungen nochmals auf speichern gehen, dann funktioniert es endlich!