I went back to an old post for a very similar issue I had.
Thanks to @generix the problem was solved back then and also in this case the approach seemed to be working! Essentially, for some reason CUDA did not complete the installation of the new Toolkit which was producing the hanging dependencies detected by autoremove.
After running sudo apt install cuda the latter were correctly installed, and I follow up removing the old CUDA Toolkit; one thing that would be helpful in these cases would be if CUDA pointed out about partial install so that users are aware of the source for this issue.
I think this post can be close for now.