It happened only a handful of times in my lifetime: once when I went to the store. It just had to be done. There was no choice. Another when heading to the beach in 2013...
Should I just leave out the colon and use a period instead?
When a colon introduces more than one sentence, capitalize all of the sentences. For example:
Some style guides (for example, AP but not Chicago) recommend capitalizing any complete sentence that follows a colon.
In your example, capitalizing “Once, when I went to the store” would clarify that you intend it as an (incomplete) sentence.
If the "once" is an example, it should be introduced with a comma rather than a colon. If you want to list all the cases, a colon would be legitimate, e.g., "It happened only a handful of times in my lifetime: once when I went to the store, once when I was conga dancing, and once when I was watching Plan 9 from Outer Space." "Once when I went to the store" is a subordinate clause, not a sentence, so the whole thing is one sentence.
The sentences following "to the store" aren't relevant. You aren't setting up a series of occurrences with them.
This reads like fiction, and so you have more creative license. I would word the passage like this to capture the list and the parenthetical within the list.
I would use the em dash instead of parentheses to keep with the informal tone. Per The Elements of Style:
"A dash is a mark of separation stronger than a comma, less formal than a colon, and more relaxed than parentheses."