When I install apps from Android Market (Play Store now) there are some apps that require special permissions and for some of them it's weird to have for example "Read phone call history" when the app is a compass or whatever...
Should I be worried? Should I uninstall an app with weird looking permissions?
Yes, you should be worried. Lots of malware disguises itself as something else that the writer thinks you might want to install so that it can get the app onto your phone. If you are at all suspicious about permissions (and reading phone history is definitely suspicious for a compass app), contact the app developer with your questions. An honest dev will get back to you.
This definitely requires some sensible judgement. If the app is from a trusted dev (Top Devloper with that symbol) then you can be rest assured that that app isn't any malware. Generally, apps which look shady in terms of title and comments are the ones you must proceed with caution.