In Kmenuedit, do entries have an option for always starting as fullscreen? Since one of the last times I reinstalled my distro, Firefox has always started as a window; I don't want it to. In the Command box, where the entry says "firefox %u", is there a parameter for fullscreen? (By the way, I don't know what %u means.)

I do not think kmenuedit can tell any arbitrary application to start fullscreen. After all, some cannot do so, and there is no standard
protocol for doing so. The X window server includes standard resource specifications such as for geometry, and many X-based programs will
obey a resource request (and it is a request, not an order) such as
"-geometry 1280x960+0+0" to start at size 1280x960 with the top left corner at (0,0). But many others won't. The firefox command,
for example, is a script that does some checking and pre-processing
and eventually calls another script, run-mozilla.sh, which only
handles certain arguments and quietly scraps the rest. Firefox remembers
sizes between sessions, so you could just make it the size you want
by dragging borders, then quit?

The %u in the command box is a placeholder for a single URL. To see
the set of possible placeholders, open kmenuedit, navigate to the firefox
entry, then select Help->What's this.. and click in the Command box. You
should get a popup describing the possible placeholders. I am not aware of anywhere else that you can find this information: the user documentation for lots of KDE is still remarkably incomplete.

So why is there a placeholder at all? A placeholder for what, you may ask? I *think* the answer is that the menu entry is not specific to the KDE menu system -- if you open up the menu and right-click on an entry, one of the options available is "Add to Desktop" and if you choose that you'll get a desktop icon. For at least some icons, you can drag'n'drop things on them, in which case the placeholder should be replaced by what you dropped. I suspect that this isn't a universal principle either, doesn't seem to work for all programs.

Something has gone wrong. My Firefox does not remember sizes between sessions.

The size is stashed in localstore.rdf, typically to be found
as ~/.mozilla/firefox/*.default/localstore.rdf (where the * is some
cryptic sequence of characters specific to your setup).

Try this:
a) do ls -l localstore.rdf and note the time it was last changed
b) start firefox, do something, quit firefox
c) repeat (a), check that the time of last change has altered

It may be corrupt on your machine for some reason; nothing's perfect! See
http://kb.mozillazine.org/Corrupt_localstore.rdf for advice about
fixing it.