I think the best way to determine whether or not your simple solution compromises performance too much is to try it out.
Something like the following should work for updating each message status.
foreach (var message in _db.Messages.Where(x => x.Status == "New"))
{
BroadcastMessage(message);
message.Status = "Read";
}
_db.SubmitChanges();
If you find this is too inefficient, you could always write a stored procedure that will select new messages and mark them as read.
It might be better to fine tune performance by adjusting the rate you are polling the database and batching messages so you broadcast a single message via SignalR for each DB query even when the DB returns multiple new messages.
If you decide to go stored proc route, here is another fairly in-depth article about using them with EF: http://msdn.microsoft.com/en-us/data/gg699321.aspx