Learn English – Conjugation of ‘shall’ in Early Modern English

It is unfortunately common for writers to attempt dialogue in Early Modern English, even though they do not know this language. This typically results in a panoply of howlers: -th and -st added randomly to verbs, thee used as the subject of sentences and thou as the object, mine used before consonants, and vocabulary used in anachronistic senses.

There's really no substitute for reading widely in the language. It's easy to get hold of texts from the period via Project Gutenberg, Google Books, the Internet Archive and so on (editions often modernize spelling but usually leave grammar and vocabulary alone). The Historical Thesaurus of the Oxford English Dictionary is a useful tool for finding vocabulary that's appropriate to a particular historical period, or if your library lacks this work, then try Google Advanced Book Search by date.

It will pay dividends if you immerse yourself in the language even as you attempt to learn its rules, and so I recommend James Greenwood's Royal English Grammar of 1737, which says (page 60):

In Engliſh there is no Change at all made of the Verbs; except in

The Second Perſon Singular of the Preſent Tenſe, and in the Second Perſon Singular of the Preter Tenſe, which Perſons are diſtinguiſhed by the Addition of eſt; as, thou burneſt, thou readeſt, thou burned'ſt, thou loved'ſt. So likewiſe

In the Third Perſon of the Preſent Tenſe, an Alteration is made by adding the ending eth, or s, (or es if the Pronunciation requires it;) as, he burneth or burns, he readeth or reads. In all the other Perſons the Word is the ſame; as, I burn, we burn, ye burn, they burn. So, I burned, he burned, we burned, ye burned, they burned, &c.

If the Preſent Tenſe ends in e, the ſt is added inſtead of eſt, in the Second Perſon, and th inſtead of eth in the Third Perſon; as, I love, thou loveſt, he loveth.

Both your examples contain solecisms:

*He dideth walk to the store.

Use "he did walk". [For example: 1687  The Compleat Office of the Holy Week 249  Noe was a a juſt and perfect man in his generations: He did walk with God.]

Also, store meaning "a place where merchandise is kept for sale" is, according to the OED, an American usage first attested in 1731, so may not be appropriate for your period. Try shop instead.

*He walkedeth to the store.

Use "he walked". [For example: 1608  J. Donne ΒΙΑΘΑΝΑΤΟΣ (1648) 169  expoſing himſelfe to certaine danger when he walked upon the water.]

I can’t find a list of all irregular Early Modern English verbs, but Sandved’s appendix to his Introduction to Chaucerian English provides a list for Middle English. (Maybe try Algeo and Pyles The Origins and Development of the English Language.)

The nub of the question, though, concerns modal verbs. Even in Anglo-Saxon (Old English), these did not take -eth in the third singular. So, compare ic gā (I go) and hē gǣð (he goes), or ic secge (I say) and hē segð (he says), with ic/hē cann (I/he can), or ic/hē mæg (I/he may). This syncretism between 1sg and 3sg was not restricted to modals (‘know’ and ‘own’ did it too), but it survived in the modals into Middle and Early Modern English, hence, your baulking at “(s)he canneth”.