* Testimony is by convicted bagman in vote-buying scheme
* Valerio made testimony seeking leniency in sentencing
* Lula calls Valerio's accusations lies (Adds denial from Lula)
RIO DE JANEIRO, Dec 11 (Reuters) - Former Brazilian President Luiz Inacio Lula da Silva knew about and used funds from a far-reaching vote-buying scheme to pay for personal expenses, according to testimony by a convicted former consultant to the ruling Workers' Party.
The testimony, reported on Tuesday by the Estado de S.Paulo newspaper, was given in September to the Brazilian attorney general's office by Marcos Valerio, an advertising executive recently convicted as a bagman in the scheme.
Valerio also testified that an aide to the former president made veiled threats when the scandal erupted in efforts to keep him quiet, the newspaper said.
According to the report, Valerio gave the testimony voluntarily in a bid to reduce his sentence after he and 24 other former Lula aides and associates were convicted in a landmark trial heard by Brazil's Supreme Court.
Lula, on a visit to Paris with President Dilma Rousseff, denied the accusations by Valerio when approached by reporters upon leaving an event on Tuesday.
"I cannot believe in lies," he said without stopping to elaborate.
Though Valerio still received a stiff 40-year prison sentence, the circumstances of his testimony are likely to cast doubt on his claims. Among other crimes, Valerio was convicted of handling the money used in the scheme, which involved payoffs to legislators in exchange for Congressional support.
The trial exposed crimes at the core of the administration of Brazil's beloved former president and was hailed as a sign that the country is growing less tolerant of the corruption long rife in local, state, and national politics.
Lula, still Brazil's most influential political figure and a possible contender for a new run at the presidency in 2014, has denied any knowledge of the scheme since it came to light in 2005, roiling the first of his two terms.
Rousseff rejected the allegations as a "deplorable" attempt to smear the image of her mentor and predecessor.
"I reject all these attempts - this isn't the first one - to try to tarnish the immense respect that the Brazilian people have for him," she said during a press conference with French President Francois Hollande. "It's deplorable."
Though Lula's legacy has been dented by the corruption scandal, the trial has done little to sap his star power - even after officials including a former treasurer of the PT, as the Workers' Party is known, and Jose Dirceu, his once-powerful chief of staff, were convicted.
That could change if the allegations made by Valerio were proven. Critics have long alleged that the scheme could not have been carried out without Lula's knowledge, or tacit approval, but so far no proof of either has surfaced.
'WE SHOULD KILL YOU'
The newspaper report said authorities already confirmed one of two deposits that Valerio alleged were made into a bank account controlled by a former Lula assistant. It also said that another Lula assistant, and now the director of the former president's foundation, at the time the scandal broke told Valerio that "there are people in the PT who think that we should kill you."
Lula's foundation declined to comment on the report. Marcelo Leonardo, Valerio's lawyer, also declined to comment.
The former president, who presided over eight years of sustained growth in Latin America's biggest country, left office in 2011 because Brazil's constitution prohibits more than two consecutive terms in the presidency. His approval ratings at the time approached 90 percent.
After a bout with throat cancer, Lula returned to politics this year and remains a friend and informal advisor to Rousseff, a former bureaucrat and minister whom he hand picked to succeed him as the party's candidate. Rousseff was unknown to most voters at the time, but Lula's endorsement ensured her victory.
While Lula has said he will not run again if Rousseff decides to stand for re-election, some analysts believe she could decline. Rousseff's primary job as president thus far has been rekindling growth in the world's sixth-largest economy, which has slowed to a crawl for most of the past two years. (Reporting by Paulo Prada in Rio, Ana Flor in Brasilia and Gerard Bon in Paris; Editing by Todd Benson and Cynthia Osterman)