Imagine something like #[deprecated], but more like its opposite: an attribute that spells out the old name of a function which has been renamed.
When the caller of the old name gets a compile error that it doesn't exist, the information contained in the attribute can helpfully inform them of the new name and how to upgrade their code.
And unlike #[deprecated], you don't need to maintain the old APIs you want to get rid of anyway.
This is something many people have wanted for a while. The general version is being able to provide user-defined library-specific lints, including automatic fixes. This particular case is one of the most common instances of that: helping users migrate from deprecated functions to their replacements.
The simplest version, as you describe, would be to point the user to the new replacement function. That much is already somewhat possible today when you use deprecated, but as you note, that's only possible if you haven't removed the APIs, so you can't easily continue helping the user migrate after you've bumped your major version and removed the API.
You can do something about this for methods by using #[doc(alias)], but not for functions. We need to extend support to functions.