Brief answer: nautilus-actions has become filemanager-actions, and you are looking for the command
fma-config-tool. Search for "actions" to find the launcher in your application menu.
Currently, the software to create custom right-click menu entries for Nautilus (and Nemo) is called "filemanager-actions". You still can install it as "nautilus-actions": that package still exists, but is now only a meta-package that will bring in the main package.
Once you installed the package, a shortcut "Filemanager-actions" will appear in your Applications, which you can search using the keyword "actions" or "fileman".
You can launch the config tool using the command
fma-config-tool. The .desktop file, which provides your Application menu entry for the tool, is
So probably you installed it just right, but you are not finding it because of the name changes. The name has changed because the tool is aimed for both nautilus and nemo. The Ubuntu Mate file manager "caja" has its own tool.