Q: Could human decision making have evolved from food finding?
A: The answer is yes, it probably could. But the more probable answer is that decision making in humans and other animals has evolved to increase the survival chance of humans and those animals and of their species. To increase the survival chance certainly requires good decision making to find food, but it also requires good decision to avoid/evade danger, to find fit mates, to protect/raise their offspring, etc. Thus, decision making has evolved to do all these necessary activities, not only food findings, with the end, common goal of to increase the survival chance (of the animals and their species).
Q: What is the smallest animal that can do decision makings? … I wonder what other animals do this sort of thing? Rather than making a choice at random?
A: Decision making in the advanced form like that exists in humans requires a nervous system with an integration center. The group of animals or Metazoans that have a nervous system is Eumetazoa, but only animals in the subgroup called Bilateria (which comprises many phyla) have an integration center (see the picture).
The integration center in the basal (more primitive) animals of each phylum is in the form of a nerve ring, a ganglion, or a group of ganglia; only in more advanced animals of each phylum is it in the form of the brain, which can be rudimentary or well developed (like those in mammals). [1-3]
So, the earliest animals that can make decisions are probably the basal animals in each phylum in Bilateria. C. elegans, which Bryan Krause mentioned in his answer, is one of these animals. It is a small, basal animal in phylum Nematoda (marked * in the picture). It has only a nerve ring connected with ganglia as an integration center. It probably can make only simple decisions and most likely without consciousness, which is different from us, human, because the structure of its integration center is too simple to create a complex function like consciousness. The earliest animals that probably can make discussions with some form of consciousness is arguably lampreys. They are small, basal animals in the phylum Chordata (marked * in the picture), class Petromyzontida. [1,3]
However, it should be noted that decision makings have been existing in more primitive forms in other animals and other living organisms for a very long time before the brain emerged. These animals/organisms are animals that have a nervous system that is only a nerve net without the brain (e.g. jellyfish, hydras, sea anemones), animals that do not have a nervous system (sponges, Trichoplax), single-cell animals, and even plants, fungi, bacteria. All these living organisms have mechanisms (such as a nerve-net or certain cellular mechanisms) to detect information in the environment and in themselves, process the information, and make appropriate (non-random) responses without using the brain.[1-6] So, with these abilities, it can be considered that they, too, can do decision makings (but in the most primitive or most basic forms). If so, it can be considered that bacteria are the smallest organisms that can make decision makings (in the most primitive form).
Roth G & Dick K [Ref 1]: Nervous systems and brains have a dual function, i.e., the maintenance of inner “vital” functions of the organism and the control of behavior of that organism within a given environment. Unicellular organisms exert the same functions and exhibit remarkably complex behaviors, although they do not possess, by deﬁnition, a nervous system. Bacteria sense nutritive substances (e.g., sugar) or toxins (e.g., heavy metal) in their environments through a large number of chemoreceptors as well as obstacles through mechanoreceptors. This diverse information is integrated and, through a chain of complex chemical reactions, drives their ﬂagella for movement.
… The bacterium has a mini-memory, by which it can compare the incoming information with previous information, and this “knowledge” determines the behavior. Thus, even in these most primitive organisms we ﬁnd the three basic components for adaptive control of behavior, i.e., a sensorium, a motorium and in between information storage and processing.”
- Roth G, Dicke U. Evolution of Nervous Systems and Brains.In: Galizia CG, Lledo P-M (eds.). Neurosciences - From Molecule to Behavior: A University Textbook. Berlin Heidelberg: Springer-Verlag; 2013:19-45. ISBN: 978-3-642-10768-9. DOI 10.1007/978-3-642-10769-6_2.
Jorgensen EM. Animal evolution: Looking for the first nervous system. Current biology. 2014 Jul;24(14):R655–R658. DOI: https://doi.org/10.1016/j.cub.2014.06.036
Feinberg TE, Mallatt J. The evolutionary and genetic origins of consciousness in the Cambrian Period over 500 million years ago. Front Psychol. 2013;4:667. DOI: 10.3389/fpsyg.2013.00667.
Renard E, Vacelet J, Gazave E, Lapébie P, Borchiellini C, Ereskovsky AV. Origin of the neuro-sensory system: New and expected insights from sponges. Integr Zool. 2009 Sep;4(3):294-308. DOI: 10.1111/j.1749-4877.2009.00167.x
Brenner ED, Stahlberg R, Mancuso S, Vivanco J, Baluska F, Van Volkenburgh E. Plant neurobiology: An integrated view of plant signaling. Trends Plant Sci. 2006 Aug;11(8):413-419. DOI: 10.1016/j.tplants.2006.06.009.
Camilli A, Bassler BL. Bacterial small-molecule signaling pathways. Science. 2006 Feb 24;311(5764):1113-1116. DOI: 10.1126/science.1121357.