finder menu "Services>>New Terminal at Folder" doesn't work
I tried it and it does work but on directories (folders) only. I know that you said you selected a folder and it refuses to work but I don't have enough knowledge to understand the files in the System responsible for the correct activity.
I might recommend turning the option off and back on again. Create a new folder and immediately right click.
To those of you who said you are still not able to achieve the goal of adding the final step, a keyboard shortcut, this second screenshot should do it.