I am wondering what the procedure with regarding when I may remove a deprecated function from a package, particularly regarding CRAN submission.
Case
I want to update the package and re-submit a new version with new functions. May I now remove the deprecated functions?
If there is no rule per se, what are best practices?
There are no formal rules for deprecating functions, although if other packages depend on your package and you break them, CRAN may be upset. In terms of best practice the folks at Bioconductor provide some nice guidelines that I try to follow whenever possible.
To answer your question "Is three months enough", I think it depends on how many people will be affected. If it is a very popular package and you've just broken everyone's code, three months sounds a bit short. If only a few people use it in a niche area, then perhaps three months is OK.
Personally, I would go for at least six months if there's not a pressing reason for removal (e.g. broken API).
You could look up the other CRAN-hosted packages which import your package. Then send an email to the maintainers of those packages letting them know you want to remove the deprecated functions. Maybe send them the new version of your package without them, and let them get their packages ready. When they say they're fine (or you get tired of waiting for a response), it should be fine to update the version on CRAN.