Titebond or PVA is fine. You can also use a couple of small dabs of superglue - but don't overdo it otherwise you may end up taking some wood with it if you have to remove it again.

If you've already deepened the notches and have decent tools to do it, then I'd always prefer to leave the nut on, deepen the notches and then file the top of the saddle down again.

But getting the neck relief sorted is the first job, then the bridge height, then the nut height and then the intonation.

If with a lower bridge height, the higher frets are choking out whilst nearer the nut the guitar plays OK, then I'd straighten the neck more, then raise the bridge height a bit and see how that feels. Ignore the 12th fret action at the moment as that is affected by the nut slots; just concentrate on getting each fret playing cleanly and not choking when you bend the strings. You don't want to go more than flat with the fretboard, so use a straight edge (if you have one, a notched straight edge is better as the fretboard itself should be slightly more even than the tops of the frets) to check. Any upward bow in the middle of the neck and you've gone too far, and take it back to flat.

You may now discover that one or two frets choke out whilst the rest are fine. The fret above each choking fret is probably slightly higher than the others. If there appears to be a gap under the fret, then support the neck under the fret with either a sandbag or a proper neck support and try tapping the fret in further with a soft hammer. This should either have a hard plastic or brass face to it but if not, then use a piece of hardwood and an ordinary hammer. Not too much force with each tap and the fret may seat itself better.

If there's no under-fret gap or tapping doesn't help, then you'll need to file the offending fret(s) down, a bit, re-profile it and then polish it.

If there are more than a couple of high frets, then it would probably be best to do a full fret levelling, reprofiling and polishing exercise (a subject in itself and you will need to get a few specialist tools).

Once the bridge is as low as you can go with all the frets playing cleanly, then that's the time to attack the nut slots. Do it before the above actions, and lowering the bridge will change the string height at the 1st fret. Not a lot, but maybe enough to cause some buzzing.

Once the slots are lowered sufficiently, and the action is decent all the way over the neck, then now's the time to look at setting the intonation. The strings are at their minimum height over the frets, so fretting a string will add the minimum amount of extra tension to the string and so the 12th fret note and harmonic will be as in tune as possible.