Could have?

When I was 12, I could bench press 100 lbs. I can now bench press 250. (This is a straight statement of fact in a past context. When the person was 12, he was able to bench press 100 lbs.)

When I was 12, I could have bench pressed 100 lbs. (There is a slight difference in sense between this and the previous sentence. This statement is more tentative than the previous one. The previous one is very definite in its statement: when he was 12, he could definitely press 100 - the implication is that he did it all the time at the age of 12. In this one, the person is less definite: when he was 12 pressing 100 was not something he did all the time, in fact, he might have never done it. But he was able to definitely press, say, 75 lbs., and so he conjectures that at 12 he was capable of pressing 100, even if he never actually did it.)

In your original post, if you change "...it was the best use I could have made of them." to "...it was the best use I could make of them.", there is a change in sense. "I could have made of them" implies an option that he exercised with respect to the savages - this is the sense he is trying to convey in the statement. "I could make of them" does not convey this sense of option.