Queueが空のときにDequeueメソッドを呼び出すと、null/Nothingが返されるのではなく、例外InvalidOperationExceptionがスローされます。　このため、Dequeueメソッドの戻り値からQueueが空だったかどうかを判断することはできません。

Queueが空の状態でDequeueメソッドを呼び出すとInvalidOperationExceptionとなる
Imports System
Imports System.Collections.Generic

Class Sample
  Shared Sub Main()
    Dim q As New Queue(Of String)()

    Console.WriteLine($"Count = {q.Count}") ' 0

    ' Queueが空の状態でDequeue操作を行うとInvalidOperationExceptionがスローされる
    Console.WriteLine(q.Dequeue())
  End Sub
End Class
実行結果
Count = 0
Unhandled exception. System.InvalidOperationException: Queue empty.
   at System.Collections.Generic.Queue`1.ThrowForEmptyQueue()
   at System.Collections.Generic.Queue`1.Dequeue()
   at Sample.Main() in /home/smdn/samplecodes/dotnet/cs/test.cs:line 12

Queueが空かどうかに関わらず、例外をスローせずにポップ操作を試行するメソッドとしてTryDequeueメソッドが用意されています。

このほか、DequeueメソッドでInvalidOperationExceptionを避けるには、Dequeueメソッドを呼び出す前にCountプロパティを参照して、要素が1つ以上格納されているかチェックするようにします。