Having come to Kolkata he had found the people were warm.
Can I make the sentence with out had and without changing the meaning. Like this:
Having come to Kolkata he found the people were warm.
Removing 'had' changes the time the sentence describes. As FumbleFingers says in the comments, 'had' is only used when you are already describing a past event, and want to put this specific sentence further in the past.
Past perfect is usually only used when telling a narrative--either telling someone about a prior event: "We went to the movies last night. He had told me last week how much he was looking forward to the Superman release..."
or in fiction, where it is standard for the entire story to be written in past tense, so telling what happened before the story started requires past perfect.