I was lvl 5-6 and she still stayed with me, I think she stays with you as long as you aren't moving to another map. You can always lvl up to 5 and do her quest.
You should be able to kill the paladins at level 3 if that’s what concerns you. I haven’t tested it personally
Not really, that smite hits hard. Although I'd wager it depends on what difficulty your game is in.
Edit: I think it's generally recommended to get Karlach when you are around lvl 4-5 anyway so you can do her quest right away. But, I always speedrun to her lol.