Kelvin-Planck statement says that, it is impossible to convert all the heat taken from a source into work. Some heat must be rejected into the sink.
You are incorrectly paraphrasing the Kelvin-Plank statement. Re-read the link. Heat can be totally converted to work in a process. That does not violate the Kelvin-Plank statement of the second law. An example is the isothermal expansion of an ideal gas. But it is not possible to have a thermodynamic cycle whose only effect is to completely convert heat to work. That would be a violation of the Kelvin-Plank statement of the second law. To quote from the link:
“It is impossible to devise a cyclically operating heat engine, the effect of which is to absorb energy in the form of heat from a single thermal reservoir and to deliver an equivalent amount of work ”.
The key phrase you left out of your paraphrased statement is “cyclically operating heat engine”.
While First Law of Thermodynamics says that, change in internal energy of a body is equal to the difference between the heat exchanged and work done.
That is correct.
Since Internal energy of a body can never be negative, does it not implies that all the heat can never be converted into work and the energy left is stored as internal energy of a body?
No. Again it is possible to convert heat completely into work in a process such that $\Delta U=0$, but not in a cycle. The energy (heat) that is not converted to work in a cycle is rejected to the surroundings in the form of heat. The net work done is the heat added minus the heat rejected. At the end of the cycle $\Delta U=0$ since the system is brought back to its original state.
Consider the Carnot cycle which is the most efficient cycle possible for converting heat to work. It begins with a reversible isothermal expansion that completely converts incoming heat from the surroundings into work. That is followed by a reversible adiabatic expansion ($Q=0$) that brings the system to a lower temperature. Then there is a reversible isothermal compression, which rejects heat to the surroundings. The cycle is completed with a reversible adiabatic compression ($Q=0$) bringing the gas back to its original state. The work done in the cycle equals the heat added during the isothermal expansion minus the heat rejected during the isothermal compression.
Please help me to know, why there was a need of Kelvin-Planck statement when First Law of Thermodynamics was already there.
The first law is a statement of the conservation of energy. Converting heat from a single reservoir completely into work in a cycle would not violate the first law since energy is conserved (heat in = work out). However, no heat engine cycle has ever been devised to completely convert heat to work (100% thermal efficiency) from a single reservoir. The Kelvin-Plank statement reflects that fact.
Hope this helps.