I would practice using an F#o7 arpeggio (F# A C Eb) resolving to G melodic minor/Gm6 in bars 4-5. Here are some examples that would work either in bar 4 or bar 6.
F# A C Eb D C Bb A / G (root of Gm)
G F F# A C Eb D C / Bb (third of Gm)
Another good one to practice is to make the ii-7b5 chord a dominant, in this case A7 or Eb7, leading to the D7. You could use C#o7 arpeggio on the A7, leading to an F#o7 arpeggio on D7, like so:
C# E G Bb A F# Eb Db / D (5th of Gm).
The A7 (instead of A-7b5) works for a few reasons. 1) It creates a stronger pull to the D7 because it's the V of D7. 2) The C# in the A7 is a blue note in G minor, which is the key center we're in for measures 5-6.
Another idea with A7 to D7 would be to use a diad of C# and Bb for the A7 (3 and b9), moving down a half step to C and A for D7 (b7 and 5), and move that down a whole step to Bb and G for G minor (b3 and 1). This sits really nicely on the G and E strings.
Getting these simple, clear resolutions under your fingers will help express the changes effectively and open up your ears to more colorful options than just using the parent scale for all related chords. You could use this same concept with bar 2, but transposed to Bo7, instead of using C melodic minor for the ii-V in bar 2.
When you get to G minor, melodic minor and G blues are really good options I think. In fact, I think it would be totally appropriate to approach bars 5-6 and the first half of bar 7 the same way you would treat bars 1-3, but in G minor instead of C minor. The tune itself actually does this: The melody over the G minor section is the same melody as the C minor section but transposed.
As for the mixolydian #11 question:
I don't think modally very much in my own playing, but if you understand how different notes work on different chords, I think you will find that you can convincingly use either mixolydian or mixolydian#11 on any of those dominants. The only difference in these scales is one has the natural 4, and the other has the #4.
If I were using the natural 4, I would probably be using it on the way to targeting the third. So, for Eb7, I might go Ab Gb G, or Ab F Gb G. I could also use Eb blues scale on the Eb7, in which case the fourth will sound totally acceptable if you use it as part of a bluesy melody.
While 4 typically wants to move down to 3, #4 is going to be inclined to go up to scale degree 5. Say you want to use this sound on the Ab7, you could go D F E D Eb C, which uses the #11 twice to surround the 5th (Eb) which then moves down to C, the third. Try that one beginning on beat one of Ab7, using 8th notes.
I think when you are still learning how to get through standard-type changes in a simple and effective way, you might want to check out some guys who play a little more simply than a player like Kurt. Guys like Hank Mobley and Dexter Gordon are really great for this. Check out their solos on If I Should Lose You and Cheese Cake, respectively, for some great ideas on minor tunes. You are sure to find lots of things that you could readily apply to How Deep Is The Ocean. Kurt's stuff will probably be a lot more meaningful after checking out some older guys approaches, as well. Bill Evans also has a great version of this tune on his Explorations album.
I hope some of that helps!