Okay, since my last post I have confirmed to my satisfaction the parentage of my grandmother's step-brothers. Their father was my great-grandfather, William Ellsworth Starr, Sr. and their mother was, indeed, Ethel Lynda Kline. I base this in my Grand Uncle Robert's and Grand Uncle Bill (William E. Starr, Jr.) birth certificates, Social Security application and the family's enumeration on the 1910 census.
I am not sure where the maiden name that was provided by my Grand Uncle Robert's daughter (found in his obituary) came from. A mystery that intrigues me; I'll be continuing my search to find the answer.