>>411です。
いろいろ試してみて、いいアドオンを見つけました。
Clean All - cache & history cleanerと言います。
https://addons.mozilla.org/ja/firefox/addon/history-cache-cleaner/

Cookieだけじゃなく、キャッシュや履歴、Local Storageなどを削除できるよくあるアドオンですが、
期間を指定して起動時に削除できます。
また、起動時じゃなく一定時間ごとに自動で削除したり、削除したい時に手動で削除することも可能です。

まだユーザー数は少ないですが、元々はChrome用のアドオンだったみたいで、
Chromeではユーザー数10万人越えでおすすめのアドオンとなっています。
FirefoxでおすすめのClear Browsing Dataも試してみましたが、起動時の削除ができません。
画面もモダンだし、個人的にもこちらの方がおすすめです。