rlang::warn() and rlang::abort() have a .frequency argument, but the least frequent they go to is once per session. "What has changed" is an interesting use case, though. I'll be interested to hear what people think!
I think I'd use {rappdirs} to store something in a package dir telling you that they've already seen it. I'd probably prompt the user to make sure it's ok to store that (and telling them that the message won't appear again).
Let us know how it goes!