Настройки постоянных ссылок mysite.com/%postname%/

Откуда взялась /category/ ? Как о неё избавится?

Это идентификатор, показывающий, что по данному адресу конечный документ не запись, а страница рубрики (архивная страница, страница списка записей).
Если Вам не нравится слово category Вы можете изменить его в настройках ссылок.
Для того что бы вообще избавиться (если действительно зачем-то хочеся вносить хаос в структуру адресов), то эта функция есть в СЕОплагинах или же можно использовать спец плагин.

А почему ссылки в меню на рубрику генерируется без category ?

Вероятно они не генерируются, а жестко где-то прошиты. Если бы генерировались они бы учитывали настройки ЧПУ.

Я правильно понимаю что должны генерироваться?

Они генерируются в любом случае, а вот ЧТО Вы вводите в меню — это другая история.
Чтобы правильно вывести используйте произвольное меню. Если там рубрики не отображаются, то на этой странице справа вверху см настройки экрана.