You're actually pretty close. Here's how to make it work, with some minor "not necessary but still good to have" improvements:
Sub test()
Dim rng As Range
Do
Set rng = Cells.Find(What:="b")
If Not rng Is Nothing Then
rng.EntireRow.Delete
Else
MsgBox ("All headers deleted")
Exit Do
End If
Loop
End Sub
The reason I added a Range object and declare it before we even enter the If loop is mostly for readability but also so we don't attempt to use .Find several times. It's unlikely this has any major impact - the compiler probably fixes this by itself. Regardless, it doesn't hurt to make it explicit in the code.
The reason you get an error after the last instance is deleted is because the code tries to .Activate an empty range. This operation isn't permitted. One solution, namely the one I've gone for here, is to check whether the range object is valid before attempting to call any of its members. If the object isn't valid, the loop will skip it altogether and we don't get any errors. The way this works is, Range.Find returns Nothing (which is a valid object state) if it doesn't find anything. You'll see in my code that I am telling the compiler to enter the loop only if rng doesn't contain Nothing.
I also removed all .Select calls, because it's not good practice. Best practice is to declare all variables explicitly and working directly on ranges. The resulting code is also shorter and easier to read.
The final edit is adding Exit Do in your Else clause. This is highly necessary since you didn't add any break condition to your Do ... Loop. Without an Exit Do somewhere, the program would toss MsgBox at you forever.
It's also possible to move from Exit Do to a more robust Do ... Loop with conditions - it could look like this:
Sub test()
Dim rng As Range
Do
Set rng = Cells.Find(What:="b")
If Not rng Is Nothing Then
rng.EntireRow.Delete
Else
MsgBox ("All headers deleted")
End If
Loop While (Not rng Is Nothing)
End Sub