The scientific definition for a fossil is that it's the preserved remains of something once-living, or evidence of its biological activity, which is more than 10,000 years old. It's a fallacy that a 'fossil' has be hundreds of thousands or millions of years old. The cut-off date broadly represents what we regard as the start of the modern Holocene era. Fossils that represent evidence of activity such as footprints are in the sub-category 'ichnofossils'. The oldest known anatomically modern human footprint ichnofossils date to around 117,000 years and were discovered in South Africa, although there are other bipedal hominin footprints from Africa dating to 3.7 million years. Near where I used to live on the East coast of England, some footprints from at least 850,000 years ago were exposed after storm-erosion of a beach.
Having said that, without some additional evidence or expert examination, it's much more probable that you have just found a curiously-shaped piece of lithified marine sediment. It's resemblance to a human footprint is not very convincing.
The shells you observed on the 'bottom' are brachiopods and they do appear to be fossilised.
