>Since starting a new game on the same cartridge erases the current game, does using a Key mean restarting your game, or does it mean that the Elite 4 will now be in Challenge mode, and you will continue your game?
You will continue the game.
>Regarding the shiny charm, I don't need to have every Pokemon in the National dex in my possession, but I need to have caught every Pokemon once (excluding event Pokemon), am I correct? I know the PC will expand once 16 boxes are filled, but I don't really want to keep Pokemon that I won't use...
You just need them all caught. Event Pokemon are excluded. Remember that evolving also counts as capturing, and you can only get some Pokemon by evolving ingame. Otherwise, just capture and release.