You don’t actually need the display:block for the border to show (apart from in IE7 and under). It will work without display:block just fine (indeed better as you won’t get the jump in the page when the border appears). You can add padding and border to inline elements but they won’t affect the flow of content around them because that is controlled by the line-height of the element and any content that exceeds the line-height just overlaps other elements and will not disturb the flow of the document.
If you really do need the element to be display:block then you should avoid causing a re-flow and not change the dimensions on hover. Instead give the element a white border by default and then just change the color only on hover and thus causing no re-flow to occur and a smooth transition to the hover state.
IE7 won’t show full padding and borders on inline elements unless you add position:relative (but that’s just a nonsense fix for a buggy browser).
So the basic answer is no you don;t need to make the elements display:block but when you add padding and border they won;t affect the floa of the document (which most of the time is what you want for inline elements.)