Question: Over time there are many past log entries (for either build or debug sessions) accumulated in the Log Navigator. How can I remove these entries?

Answer: 
Turns out this is what you have to do:

1. Go to Organiser
2. Go to Project tab
3. Select your project
4. Select the Delete button on the right hand side where it says "Derived Data includes Index, build output and logs"
5. Close the project or workspace.
6. Re-open the project or workspace.

Note that the comments are correct. This approach does delete the index, and build output in addition to the logs. It does warn that "The first indexing and rebuild of a project after that may be slower".
This works in Xcode 5 and may work in Xcode 4:

If you just want to clear the million entries in the Log Navigator, try closing the project/workspace and reopening it. (Close, Open Recent)

This cleared the Log Navigator for me, was less effort than doing anything in the Organizer window, and did not delete the index or build output.