As long as you've got that "*" in there, then the only thing that I could imagine that would make much difference would be to change your index definition to this:
CREATE NONCLUSTERED INDEX [CommonQueryIndex] ON [dbo].[Heartbeats]
(
[DateEntered] ASC,
[DeviceID] ASC
)INCLUDE (ID, IsWebUp, IsPingUp, IsPUp)
WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
As I noted in the comments, it should use that index, but if it doesn't you can persuade it to with either an ORDER BY or an index hint.