The earliest Pokemon with the Cute Charm ability that can be obtained in Pearl is Lopunny by catching and evolving a Buneary in Eterna Forest. This area can be accessed after beating Mars in the Valley Windworks building. This area is after the first gym. Buneary can be difficult to evolve, since it needs to have such high friendship. It also has the chance to evolve into a Lopunny with the Klutz ability.
Another Pokemon I recommend is Cleffa. It can be found in the Route 207 entrance to Mt. Coronet. This area can be accessed after you beat the second gym and get the bike. However, unlike Buneary which has a 50/50 chance to be Male, Cleffa has a 25% chance to be Male and a 75% chance to be Female. Cleffa doesn't need to evolve to get the Cute Charm ability, but it can have the Magic Guard ability too.
Hope this helped.