In GNU grep, egrep and fgrep are shell scripts anyway; starting with 3.8, these are where the obsolescence warning is produced:
#!/bin/bash
cmd=${0##*/}
echo "$cmd: warning: $cmd is obsolescent; using grep -E" >&2
exec grep -E "$@"
Replacing them with your own version is fine; the previous version was
#!/bin/sh
exec grep -E "$@"
(with an obvious variant for fgrep).
The only aspect to watch out for is that your packaging system still “owns” the egrep and fgrep binaries, so you’ll lose your changes whenever the package is upgraded. To avoid that, you can tell the packaging system that it no longer owns the files; in Debian derivatives, run
sudo dpkg-divert --divert /usr/bin/egrep.original --rename /usr/bin/egrep
sudo dpkg-divert --divert /usr/bin/fgrep.original --rename /usr/bin/fgrep
This will cause the packaging system to always rename the packaged file to ?grep.original.
(Curious readers may want to read the bug report which led to these warnings, and a few bug reports filed as a result.)