Debug.Log doesn't work properly in a ContextMenu function

I've seen similar behaviors with logging frameworks; the reason is very likely that log statements are somehow batched for performance reasons (e.g. only putting out logging "once per frame" which would mean all log-statements from one frame are sent to the console in a single step; or it may even be that the console batches the log statements in one way or another).

Anyways, instead of waiting for the log statements, you could work with timestamps (which would be what I'd recommend for logging such things anyways). One very convenient way of doing that is using the Stopwatch class the .NET framework provides. For using this, you need to include the namespace System.Diagnostics (which is in system.dll - which for editor scripts doesn't matter but you might be careful using this in Web Players, see also Reducing File Size - Reducing included dlls in the Web Player).

using System.Diagnostics;
[...]
[ContextMenu("Calculate PVS")]
void CalculatePVS()
{
    Stopwatch sw = new Stopwatch();
    sw.Start();
    VeryExpensiveFunction();
    Debug.Log(string.Format("Calculating the PVS - first call took {0}ms", 
                            sw.ElapsedMilliseconds));
    VeryExpensiveFunction();
    Debug.Log(string.Format("Calculating the PVS DONE - took {0}ms", 
                            sw.ElapsedMilliseconds));
}

If you don't want to work with classes from System.dll, you could also create yourself a simple helper class using DateTime.Now or directlyuse DateTime.Now in your code (really depends on how much time-tracking you need to do).

I don't know whether there's a solution to making the Debug messages show up, but if you're broadly looking for some way to get progress feedback during a long-running editor script, you can use EditorUtility.DisplayProgressBar. In your case you'd probably use it something like this:

[ContextMenu("Calculate PVS")]
void CalculatePVS()
{
    EditorUtility.DisplayProgressBar ("Calculating the PVS", "Calculating - 0%", 0)
    VeryExpensiveFunction();
    EditorUtility.DisplayProgressBar ("Calculating the PVS", "Calculating - 50%", 0.5f)
    VeryExpensiveFunction();
    EditorUtility.DisplayProgressBar ("Calculating the PVS", "Calculating - 100%", 1)
}

Of course, it would be better to have more finely-stepped progress updates actually inside your VeryExpensiveFunction! You also need to use EditorUtility.ClearProgressBar when all your operations have finished to hide the progress bar.