I forgot to answer one question you asked:
Should I actually instead go in and remove the folders as well and then try reinstalling?
No. This will change nothing for menus.
Conceptually, menu items are created / refreshed when Joomla starts installing the component. It reads the menu structure from the XML manifest which is included with the component package, removes the old menu items for the component which do not exist in the manifest, adds the new menu items from the manifest, and updates the existing ones from the manifest. This is part of the core Joomla code.
The only reason Joomla would not be able to update the menu items is if the menu items table, which is a tree structure, was broken in a way Joomla's Joomla\CMS\Table\Nested code cannot work around. However, using the Rebuild button fixes that problem.
This leaves me with two possible problems.
One is that you try to install the wrong version of Akeeba Backup, that's why I told you to install version 9.
The other possible problem is that your database structure is completely broken and no menu items can be created. Try installing another component which creates nested menu items (not just a single item under Components). If you get a problem creating menus, yes, your database table is broken.
Nicholas K. Dionysopoulos
Lead Developer and Director
🇬🇷Greek: native 🇬🇧English: excellent 🇫🇷French: basic • 🕐 My time zone is Europe / Athens
Please keep in mind my timezone and cultural differences when reading my replies. Thank you!