"We had already eaten fruit"
Yeah. There was some disagreement about whether using -lisha- for the pluperfect is normal and acceptable, but adding -ya- here is fine. It's a little bit more emphatic and more likely to be interpreted as making it "the fruit", but still fine.
(And the non-controvertial form of the pluperfect would be tulikuwa tumekula = we had eaten. This -lisha- thing seems nice and compact though.)